Skip to main content

21. Network Delay Time

mediumAsked at Swiggy

Compute the time it takes for a signal to reach every node from a source.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given a list of directed edges times[i] = [u, v, w] meaning signal travels from u to v in w time. Starting from node k, return the time it takes for all n nodes to receive the signal, or -1 if some node is unreachable.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • 1 <= w_i <= 100

Examples

Example 1

Input
times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
Output
2

Example 2

Input
times=[[1,2,1]], n=2, k=2
Output
-1

Approaches

1. Bellman-Ford

Relax every edge n-1 times.

Time
O(n * E)
Space
O(n)
const dist=Array(n+1).fill(Infinity); dist[k]=0;
for (let i=0;i<n-1;i++)
  for (const [u,v,w] of times)
    if (dist[u]+w<dist[v]) dist[v]=dist[u]+w;
const m=Math.max(...dist.slice(1));
return m===Infinity?-1:m;

Tradeoff:

2. Dijkstra with min-heap

Classic shortest-paths-from-source with a priority queue. Pop the smallest tentative distance, relax outgoing edges, push improved neighbors. Answer is max final distance.

Time
O(E log V)
Space
O(V + E)
function networkDelayTime(times, n, k) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const pq = [[0, k]];
  while (pq.length) {
    pq.sort((a, b) => b[0] - a[0]);
    const [d, u] = pq.pop();
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) { dist[v] = d + w; pq.push([d + w, v]); }
    }
  }
  const m = Math.max(...dist.slice(1));
  return m === Infinity ? -1 : m;
}

Tradeoff:

Swiggy-specific tips

Swiggy uses Dijkstra-style shortest-path questions to gauge whether you can model real-time dispatch latency from a hub across the courier network.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Network Delay Time and other Swiggy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →