Skip to main content

20. Network Delay Time

mediumAsked at Expedia

Find the time for a signal to reach all nodes from a source — Expedia uses the same Dijkstra logic to compute earliest-arrival flight connections across their global route graph.

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

Problem

You are given a network of n nodes labeled 1 to n. You are given times, 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. 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, return -1.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= u, v <= n
  • 0 <= w <= 100
  • All (u, v) pairs 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 reaches node 1 and 3 at time 1, then node 4 at time 2.

Example 2

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

Approaches

1. Bellman-Ford

Relax all edges n-1 times. Simple to implement but O(V*E) — too slow for dense flight graphs.

Time
O(n * E)
Space
O(n)
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; use a priority queue to greedily settle shortest distances. O((V+E) log V) — standard for sparse flight-route graphs.

Time
O((V + E) log V)
Space
O(V + E)
function networkDelayTime(times, n, k) {
  const graph = new Map();
  for (let i = 1; i <= n; i++) graph.set(i, []);
  for (const [u, v, w] of times) graph.get(u).push([v, w]);

  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;

  // Min-heap: [cost, node]
  const heap = [[0, k]];

  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [cost, u] = heap.shift();
    if (cost > dist[u]) continue;
    for (const [v, w] of graph.get(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:

Expedia-specific tips

Expedia grades this heavily on your ability to name Dijkstra by pattern, not just produce working code. Explain why the priority queue pulls the minimum-cost node next and how that maps to choosing the cheapest flight leg at each hop. They also want to hear you flag the negative-weight caveat (Bellman-Ford then).

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

Practice these live with InterviewChamp.AI →