Network Delay Time | Leetcode-743 | GOOGLE | Graph Concepts & Qns - 28 | Explanation+Coding

This is the 28th Video on our Graph Concepts Playlist.
Since we have studied Dijkstra's Algorithm, now it's time to brush it by solving problems on it.
In this video we will solve another very famous problem "Network Delay Time".

If you have been following my "Graph Concepts & Qns" playlist , then these will become very easy. Make sure to watch from the beginning of this playlist to master graphs.
in the easiest way possible.

Problem Name : Network Delay Time
Company Tags : GOOGLE

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[AnjuGupta-szuk]

I was able to solve it my own without watching video, it was only possible because of concept clarity gain by watching this playlist..

[oqant]

did it on my 💪💪
.just made few mistakes and came here to correct them

[souravjoshi]

Thanks a lot man. You are back on graph Concepts playlist ❤‍🔥

[SrishtiKapoor-dw]

I was able to solve this on my own.. Thank you so much Guruji ❤❤

[phoddaal]

Thank you so much sir, for making this scary topic very easy for us. 😍

[floatingpoint]

i was just looking to solve this question. thanks for your explanation it was really helpful

[Xp-Sam]

Hey MIK, I am confused between array of vector representation of a graph and unordered_map representation. Which is good and efficient? I heard that sometimes unordered_map gives O(N) for lookup and insertion in worst cases, but at the same time it is more flexibe for creating the graph(like when the nodes are numbered random, or they are not integers at all)

[Abhay]

bhaiya maine poora solution bina dekhe liya sbb kuchh shi tha but mai yha confuse hun ki hmne pq.push({0, k}) me phle distance and fir node push kiya but

adjacency list me hmne adjDistance me v.second and adjNode me v.first kyun liya mtlb push ke time alag kyun and adjacency me pop ke time alag order kyu




code-


class Solution {
public:
int times, int n, int k) {
// we create dijkastra's algorithm for finding result vector
unordered_map<int, vector<pair<int, int>>>adj;
for(auto & it : times){
int u = it[0];
int v = it[1];
int w = it[2];
adj[u].push_back({v, w}); // u ke and v ie, u->v
}

// k is source
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
vector<int>result(n+1, INT_MAX);
result[k] = 0; //distance, node

pq.push({0, k});

while(!pq.empty()){

int node = pq.top().second;
int distance = pq.top().first;
pq.pop();

for(auto & v : adj[node]){

int adjNode = v.second;
int adjDistance = v.first;

if(adjDistance + distance < result[adjNode]){
result[adjNode] = adjDistance + distance;
pq.push({adjDistance + distance, adjNode});
}

}


}
int maxi = INT_MIN;
for(int i=1; i<=n; i++){
maxi = max(maxi, result[i]);
}
if(maxi != INT_MAX){
int ans = maxi - result[k];
return ans;
}
return -1;

}
};

[kartikforwork]

you sometime make adj path of u-->v and v-->u both, but sometimes not, i am little confuse.... can anyone explain

[gocrazy]

Able to solve it by my own

"class Solution {
public:
int times, int n, int k) {
int source = k;

// Create the adjacency list
unordered_map<int, vector<pair<int, int>>> adj;

for(auto &it : times) {
int u = it[0];
int v = it[1];
int t = it[2]; // weight -> time

// u -> v, given directed edges
adj[u].push_back({v, t});
}

// Min-heap for traversing
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

// Stores the distance from the source to the rest of the nodes (indexes)
// result vector will store the distance of each node (as indexes) from the source in result[idx]
vector<int> result(n + 1, INT_MAX);

// Source to source distance when destination = source
result[source] = 0;
pq.push({0, source}); // distance, source

while (!pq.empty()) {
pair<int, int> top = pq.top();
pq.pop();

int dist = top.first;
int u = top.second;

for (auto &v : adj[u]) {
int adjNode = v.first;
int adjDist = v.second;

// Distance between source to adjNode
if (dist + adjDist < result[adjNode]) {
result[adjNode] = dist + adjDist;
pq.push({dist + adjDist, adjNode});
}
}
}

// Finding the maximum time it will take to reach the farthest node
int mx = -1;

for (int i = 1; i <= n; i++) {
if (result[i] == INT_MAX) {
return -1;
}
mx = max(mx, result[i]);
}

return mx;
}
};
"

[MakeuPerfect]

last mein time complexity explain kar dena bhaiya

[ujjwalsharma]

Hello mik.. Plss solve question.
2 keys keyword leetcode question

[AYJ]

class Solution {
record Pair(int node, int dist){}
public int networkDelayTime(int[][] times, int n, int k) {
var adj = new HashMap<Integer, ArrayList<Pair>>();
var res = new int[n + 1];
Arrays.fill(res, Integer.MAX_VALUE);
res[k] = 0;

for(int[] time : times)
adj.computeIfAbsent(time[0], l -> new ArrayList<>()).
add(new Pair(time[1], time[2]));
PriorityQueue<Pair> minHeap = new PriorityQueue<>((x, y) -> x.dist - y.dist);
minHeap.offer(new Pair(k, 0));

while(!minHeap.isEmpty()){
Pair p = minHeap.poll();

if(!adj.containsKey(p.node)) continue;

for(Pair neigh : adj.get(p.node)){
int v = neigh.node;
int w = neigh.dist;
if(p.dist + w < res[v]){
res[v] = p.dist + w;
minHeap.offer(new Pair(v, res[v]));
}
}
}
int max = Integer.MIN_VALUE;
for(int i = 1; i < res.length; i++){
if(res[i] == Integer.MAX_VALUE) return -1;
max = Math.max(res[i], max);
}
return max;
}
}