Skip to main content

16. Network Delay Time

mediumAsked at Tesla

Find how long a signal takes to reach all nodes from a source — Tesla applies this shortest-path reasoning to model charging-network latency and route EV fleets to the fastest available Supercharger under real traffic conditions.

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 directed travel-time edges where times[i] = [ui, vi, wi] means a signal travels from node ui to vi in wi time. Given a source node k, return the minimum time for all n nodes to receive the signal. Return -1 if it is impossible.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • 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: Node 2 reaches 1 and 3 in time 1, then 4 via 3 in time 2. All nodes reached by time 2.

Example 2

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

Approaches

1. Bellman-Ford

Relax all edges n-1 times. Simple but O(V*E), acceptable for small constraint sizes.

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 with min-heap

Greedy shortest-path using a priority queue. Visits each node once in O((V+E) log V).

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: [distance, node]
  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.get(u)) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }

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

Tradeoff:

Tesla-specific tips

Tesla interviews on shortest-path problems because the same algorithm class drives Supercharger routing and fleet dispatch. They'll push you on negative-weight awareness (Bellman-Ford vs Dijkstra) and ask how you'd extend this to time-varying edge weights as traffic conditions change. Mention that the max-dist result maps directly to worst-case charging ETA across the fleet.

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

Practice these live with InterviewChamp.AI →