Skip to main content

22. Network Delay Time

mediumAsked at CircleCI

Find the time for a signal to reach all nodes using Dijkstra's algorithm, directly modeling how CircleCI measures end-to-end latency across distributed build infrastructure.

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

Problem

Given a network of n nodes with directed weighted edges times[i] = [u, v, w], and a source node k, return the time for all n nodes to receive the signal from k. Return -1 if unreachable.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • 1 <= w <= 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 all edges n-1 times to find shortest paths.

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] + 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

Use a priority queue to greedily process the nearest unvisited node, achieving O((V+E) log V) — the right choice for sparse CI infrastructure graphs.

Time
O((V+E) log V)
Space
O(V+E)
function networkDelayTime(times, n, k) {
  const graph = {};
  for (let i = 1; i <= n; i++) graph[i] = [];
  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 simulation via sorted array (small n)
  const heap = [[0, k]];
  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:

CircleCI-specific tips

CircleCI maps this to measuring build artifact propagation across datacenter regions — explain Dijkstra's greedy guarantee and how you'd handle negative-weight edges (hint: Bellman-Ford or SPFA).

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

Practice these live with InterviewChamp.AI →