Skip to main content

26. Network Delay Time

mediumAsked at Asana

Find the time for a signal to reach all nodes in a weighted directed graph — Asana maps this to computing the latest a notification will propagate across all team members in a project's dependency-notification chain.

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

Problem

You are given a network of n nodes labeled 1 to n, a list of travel-time weighted directed edges times where times[i] = [ui, vi, wi], and a starting node k. Return the minimum time it takes for all nodes to receive the signal from k. If impossible, return -1.

Constraints

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

Examples

Example 1

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

Explanation: Signal from 2 reaches 1 in 1, 3 in 1, and 4 in 2. Max = 2.

Example 2

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

Explanation: No edge from 2 to 1 — node 1 is unreachable.

Approaches

1. Bellman-Ford (simpler, handles negative weights)

Relax all edges n-1 times. Shortest path from k to every node. Check if any node remains 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;
      }
    }
  }

  let maxDist = 0;
  for (let node = 1; node <= n; node++) {
    if (dist[node] === Infinity) return -1;
    maxDist = Math.max(maxDist, dist[node]);
  }
  return maxDist;
}

Tradeoff:

2. Dijkstra with min-heap (optimal for non-negative weights)

Use a priority queue seeded with [0, k]. Greedily settle the nearest unvisited node. Stop when all nodes are settled or the queue is empty.

Time
O((V + 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;

  // Min-heap via sorted array (interview-friendly; use a real heap in production)
  const pq = [[0, k]]; // [cost, node]

  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [cost, node] = pq.shift();
    if (cost > dist[node]) continue;
    for (const [nb, w] of adj[node]) {
      const newCost = cost + w;
      if (newCost < dist[nb]) {
        dist[nb] = newCost;
        pq.push([newCost, nb]);
      }
    }
  }

  let maxDist = 0;
  for (let node = 1; node <= n; node++) {
    if (dist[node] === Infinity) return -1;
    maxDist = Math.max(maxDist, dist[node]);
  }
  return maxDist;
}

Tradeoff:

Asana-specific tips

Asana interviewers frame this as 'signal propagation across a workflow' — the answer is the maximum over all shortest paths from the source, because every node must be reached. Name the algorithm: Dijkstra for non-negative weights (all weights here are >= 0). Explain the 'max of shortest paths' reduction clearly — that insight is worth as many points as the code itself. If asked to generalize to negative weights, Bellman-Ford or SPFA; and flag that Dijkstra would require potential-based reweighting (Johnson's algorithm).

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

Practice these live with InterviewChamp.AI →