Find the City With the Smallest Number of Neighbors at a Threshold Distance | 3 Ways | Leetcode 1334
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 53rd Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
Dijkstra's - • Dijkstra's Algorithm |...
Bellman-Ford - • Bellman-Ford Algorithm...
Floyd Warshall - • Floyd Warshall Algorit...
In this video we will try to solve a very good Graph Problem : Find the City With the Smallest Number of Neighbors at a Threshold Distance | 3 Approaches | Leetcode 1334 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Find the City With the Smallest Number of Neighbors at a Threshold Distance | 3 Approaches | Leetcode 1334 | codestorywithMIK
Company Tags : Amazon, Microsoft
My solutions on Github(C++ & JAVA) -
Dijkstra's - github.com/MAZ...
Bellman-Ford - github.com/MAZ...
Floyd Warshall - github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Dijkstra's Algorithm
Purpose: To find the shortest paths from a source city to all other cities.
Implementation:
Uses a priority queue to process nodes in order of increasing distance.
Initializes the distances to all cities as infinity, except for the source city (distance 0).
Iteratively updates the shortest paths by exploring adjacent nodes.
Usage in the Solution: Computes shortest paths from each city to every other city, fills the shortest path matrix, and determines the city with the fewest reachable cities within a given distance threshold.
Bellman-Ford Algorithm
Purpose: To find the shortest paths from a source city to all other cities, particularly useful for graphs with negative weights (though not needed here).
Implementation:
Initializes distances to all cities as infinity, except for the source city (distance 0).
Relaxes edges repeatedly (n-1 times) to ensure shortest paths are found.
Ensures bi-directional edges are processed for undirected graphs.
Usage in the Solution: Computes shortest paths from each city to every other city, fills the shortest path matrix, and determines the city with the fewest reachable cities within a given distance threshold.
Floyd-Warshall Algorithm
Purpose: To find the shortest paths between all pairs of cities.
Implementation:
Initializes a distance matrix with direct edge weights and sets the distance to itself as zero.
Uses three nested loops to update the shortest paths, considering each node as an intermediate point.
Continuously updates the matrix to ensure it contains the shortest paths between all pairs of nodes.
Usage in the Solution: Computes shortest paths between all pairs of cities, fills the shortest path matrix, and determines the city with the fewest reachable cities within a given distance threshold.
Common Steps
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Thank you bhaiya for the 1 year long journey of me with you. I am proud to tell you that I have reached the level of a knight now.
If any new person is wondering, will mik be enough? Yes, given that you come here daily.
Another thing when he says to code the brute force yourself, he really means it.
That helped me improve my implementation skills.
So do that too.
Thank you Mik ❤❤❤!
I have added the screenshots on LinkedIn 😊
Congratulations and keep it up ❤️
Guys, let’s congratulate him for this achievement.
Congratulations bro
Congrats Bro
congrats bro
kampai!!
Thank you so much MIK. I have learned so much from you. You are a great instructor.
Your graph playlist is one of the best playlists of graph i have ever gone through. A treasure.
bhai ek video rabin karp algo k upr bna do jse tumne kmp Pe bnayi
True Rabin Karp aur khaskar Rolling Hash ki playlist chahiye
You are so good
Thanks a lot bhaiya ❤❤
was able to solve it on my own just because of your graphs concept playlist
Still came here to see your approach ❤❤
bhaiya can you please make a playlist on recursion on binary trees?
Hi Thanks for all the solutions , even though I have studied Dijkstra,I'm not able to undertand Leetcode 2662 (Minimum Cost of a Path With Special Roads)can you make a video on it please
please make more videos on tries playlist .
Bhaiya mai dp concept series kar raha hu please uske pdf upload kar do sare lecture ke revision me pdf bahut help karta hai
sir dsa sheet kab banaoge
Yes sir much needed
i am java user i see u r respo. pls dont stop that habit
sir , can u please tell the mistake , getting tle at 568/581
class Solution {
public:
long long dij(unordered_map&adj,char &s, char &t)
{
priority_queuepq;
vectordist(26,INT_MAX);
pq.push({0,s});
dist[s-97]=0;
while(!pq.empty())
{
char node=pq.top().second;
int d=pq.top().first;
pq.pop();
for(auto &x:adj[node])
{
if(d+x.second
bhiya is cooking food in background pressure cooker 🙂
class Solution {
public:
int findTheCity(int n, vector& edges, int distanceThreshold) {
vector mat(n,vector(n,0));
for(int i = 0;i < n; i++) mat[i][i] = 10001;
for(auto vec : edges){
int u = vec[0];
int v = vec[1];
int wt = vec[2];
mat[u][v] = wt;
mat[v][u] = wt;
}
for(int i = 0;i < n; i++){
for(int j = 0; j < n; j++){
if(mat[i][j] == 0) mat[i][j] = 10001;
}
}
// for(int i = 0;i < n; i++){
// for(int j = 0; j < n; j++){
// cout
Sir please make a solution video on this :- Leetcode 2045. Second Minimum Time to Reach Destination (HARD) . my code was :- #include
using namespace std;
class Solution {
public:
int secondMinimum(int n, vector& edges, int time, int change) {
// Create an adjacency list to represent the graph
vector adj(n + 1);
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].emplace_back(v, time);
adj[v].emplace_back(u, time);
}
// Initialize distances and visited arrays
vector dist(n + 1, INT_MAX);
vector visited(n + 1, 0);
// Priority queue for Dijkstra's algorithm
priority_queue pq;
// Start at vertex 1
dist[1] = 0;
pq.emplace(0, 1);
while (!pq.empty()) {
int curr = pq.top().second;
pq.pop();
if (visited[curr]) continue;
visited[curr] = 1;
for (const auto& neighbor : adj[curr]) {
int v = neighbor.first;
int weight = neighbor.second;
// Calculate the waiting time at the current vertex
int waitTime = (dist[curr] / change + 1) * change;
// Update the distance to the neighbor
int newDist = dist[curr] + weight + waitTime;
if (newDist < dist[v]) {
dist[v] = newDist;
pq.emplace(newDist, v);
}
}
}
return dist[n-1];
}
};
/* Leetcode POTD - 27th July, 2024 */
/* Again a problem of Floyd-Warshal Algo */
/* My code - If you have any questions, ask in reply. Will be glad if this helps anybody */
class Solution {
public void createGraph(int n, int[][] mat, char[] original, char[] changed, int[] cost){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i != j) mat[i][j] = (int)1e9;
}
}
for(int i = 0; i < original.length; i++){
int u = original[i] - 'a';
int v = changed[i] - 'a';
int c = cost[i];
mat[u][v] = Math.min(mat[u][v], c);
}
}
public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
int n = 26;
int[][] mat = new int[n][n];
createGraph(n, mat, original, changed, cost);
for(int via = 0; via < n; via++){
for(int row = 0; row < n; row++){
if(mat[row][via] < (int)1e9){
for(int col = 0; col < n; col++){
if(row != via && col != via){
if(mat[via][col] < (int)1e9){
mat[row][col] = Math.min(mat[row][col], mat[row][via] + mat[via][col]);
}
}
}
}
}
}
long result = 0;
for(int i = 0; i < source.length(); i++){
int u = source.charAt(i) - 'a';
int v = target.charAt(i) - 'a';
if(mat[u][v] == (int)1e9) return -1L;
result += mat[u][v];
}
return result;
}
}
in java dijkstra give TLE?
No it passes
below code copied from MIK's github link)
class Solution {
// Dijkstra's algorithm to find shortest paths from a source city
void dijkstra(int n, Map adj, int[] result, int S) {
PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(a -> a[0]));
pq.add(new int[] {0, S});
Arrays.fill(result, Integer.MAX_VALUE);
result[S] = 0; // Distance to source itself is zero
// Process nodes in priority order
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0];
int node = top[1];
if (adj.get(node) == null) continue; // Check if adjacency list is null
for (int[] p : adj.get(node)) {
int adjNode = p[0];
int dist = p[1];
if (d + dist < result[adjNode]) {
result[adjNode] = d + dist;
pq.add(new int[] {d + dist, adjNode});
}
}
}
}
int getCityWithFewestReachable(int n, int[][] shortestPathMatrix, int distanceThreshold) {
int cityWithFewestReachable = -1;
int fewestReachableCount = Integer.MAX_VALUE;
// Count number of cities reachable within the distance threshold for each city
for (int i = 0; i < n; i++) {
int reachableCount = 0;
for (int j = 0; j < n; j++) {
if (i != j && shortestPathMatrix[i][j] new ArrayList()).add(new int[] {start, weight});
}
// Compute shortest paths from each city using Dijkstra's algorithm
for (int i = 0; i < n; i++) {
dijkstra(n, adj, shortestPathMatrix[i], i);
}
return getCityWithFewestReachable(n, shortestPathMatrix, distanceThreshold);
}
}
Please upload 3213 soln
/* 2 solutions - Glad if this helps anybody */
/* 1st Approach usign Djikstra Algo - will give TLE */
class Solution {
static class Pair{
int node, weight;
Pair(int n, int w){
this.node = n;
this.weight = w;
}
}
static class Tuple implements Comparable{
int first, second;
Tuple(int f, int s){
this.first = f; //dist
this.second = s; //node
}
public int compareTo(Tuple next){
if(this.first != next.first){
return Integer.compare(this.first, next.first);
}
else{
return Integer.compare(this.second, next.second);
}
}
}
public void createGraph(ArrayList graph[], int[][] edges, int n){
for(int i = 0; i < n; i++){
graph[i] = new ArrayList();
}
for(int i = 0; i < edges.length; i++){
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
graph[u].add(new Pair(v, w));
graph[v].add(new Pair(u, w));
}
}
public int f(ArrayList graph[], int start, int dist, int n){
int[] cost = new int[n];
Arrays.fill(cost, (int)1e9);
cost[start] = 0;
PriorityQueue q = new PriorityQueue();
q.add(new Tuple(0, start));
HashSet nodes = new HashSet();
while(!q.isEmpty()){
int curDist = q.peek().first;
int curNode = q.peek().second;
q.remove();
for(int i = 0; i < graph[curNode].size(); i++){
int adjNode = graph[curNode].get(i).node;
int adjWt = graph[curNode].get(i).weight;
int newDist = curDist + adjWt;
if(newDist
Hi Thanks for all the solutions , even though I have studied Dijkstra,I'm not able to undertand Leetcode 2662 (Minimum Cost of a Path With Special Roads)can you make a video on it please