Skip to main content

21. Network Delay Time

mediumAsked at Lyft

Find how long a signal takes to reach all nodes — Lyft applies the same Dijkstra logic to propagate ETA updates across its real-time driver-location graph when dispatch events fire from a central node.

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

Problem

You are given a network of n nodes labeled 1 to n and a list of travel times as directed edges times[i] = [u, v, w], where u is the source node, v is the target node, and w is the time it takes for a signal to travel from u to v. We will send a signal from a given node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all n nodes to receive the signal, return -1.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= u, v <= n
  • u != v
  • 0 <= w <= 100
  • All pairs (u, v) are unique

Examples

Example 1

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

Explanation: Node 2 sends to node 1 (time 1) and node 3 (time 1). Node 3 then sends to node 4 (time 1). The maximum shortest-path time is 2.

Example 2

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

Approaches

1. Brute force (Bellman-Ford)

Relax all edges n-1 times to find shortest distances from source k. Return the max; return -1 if any node is unreachable.

Time
O(V * E)
Space
O(V)
function networkDelayTime(times, n, k) {
  const dist = new 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] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }
  const max = Math.max(...dist.slice(1));
  return max === Infinity ? -1 : max;
}

Tradeoff:

2. Dijkstra with min-heap

Build adjacency list, run Dijkstra from k using a min-heap. Greedily settle each node with the shortest known distance. Return the maximum settled distance; -1 if any node unreachable.

Time
O((V + E) log V)
Space
O(V + E)
function networkDelayTime(times, n, k) {
  const graph = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) graph[u].push([v, w]);

  // Min-heap: [distance, node]
  const heap = [[0, k]];
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;

  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift();
    if (d > dist[u]) continue;
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }

  const max = Math.max(...dist.slice(1));
  return max === Infinity ? -1 : max;
}

Tradeoff:

Lyft-specific tips

Lyft interviewers often frame this as 'how quickly can a dispatch event reach all driver nodes in a region graph.' They want to see you articulate Dijkstra's greedy invariant cleanly — 'once we settle a node, its distance is final' — before writing code. Mention that in production Lyft uses a priority queue backed by a Fibonacci heap for dense city graphs, but for interview purposes an array-based min-heap is expected.

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 Lyft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →