Skip to main content

21. Network Delay Time

mediumAsked at Instacart

Find the time for a signal to reach all nodes in a weighted graph — Instacart uses this exact shortest-path pattern to estimate worst-case delivery propagation across its fulfillment network.

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

Problem

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

Constraints

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

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 all edges n-1 times. The max distance to any reachable node is the answer; return -1 if any node remains unreachable.

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 maxDist = Math.max(...dist.slice(1));
  return maxDist === Infinity ? -1 : maxDist;
}

Tradeoff:

2. Dijkstra (min-heap)

Use a priority queue seeded with the source node. Greedily settle the nearest unsettled node; stop early once all nodes are settled.

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]);

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

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

  function heapPush(item) {
    heap.push(item);
    heap.sort((a, b) => a[0] - b[0]);
  }
  function heapPop() {
    return heap.shift();
  }

  while (heap.length) {
    const [d, u] = heapPop();
    if (d > dist[u]) continue;
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heapPush([dist[v], v]);
      }
    }
  }

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

Tradeoff:

Instacart-specific tips

Instacart's routing team thinks about delivery propagation latency across warehouse-to-store edges. Interviewers want Dijkstra here, not Bellman-Ford — and they'll push on why: directed graph, non-negative weights, and early termination once all nodes settle. Mention that in practice the heap is a real priority queue structure, not an array sort.

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

Practice these live with InterviewChamp.AI →