Skip to main content

743. Network Delay Time

mediumAsked at Cisco

Network Delay Time is the most on-brand Cisco interview question — it's literally framed as 'how long does a signal take to reach every node in a network?' The interviewer is checking whether you reach for Dijkstra's algorithm and whether you implement it with a binary heap rather than a linear scan.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco Software Engineer onsite reports consistently cite this as the 'Cisco favorite' shortest-path round.
  • Levels.fyi (2025-12)— Cited in Cisco SDE-II and Network Software Engineer interview write-ups.
  • Blind (2025-08)— Cisco interview thread lists Network Delay Time as the most common Dijkstra problem in their loop.

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 times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. 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 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique.

Examples

Example 1

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

Explanation: From node 2, signal reaches 1 in 1, 3 in 1, then 4 in 2. The slowest arrival is 2.

Example 2

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

Example 3

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

Explanation: Node 1 is unreachable from node 2.

Approaches

1. Brute-force Bellman-Ford

Initialize all distances to Infinity except dist[k] = 0. Relax every edge n-1 times.

Time
O(V*E)
Space
O(V)
function networkDelayTimeBF(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;
    }
  }
  let max = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    max = Math.max(max, dist[i]);
  }
  return max;
}

Tradeoff: Simpler to code, works even on graphs with negative weights (Cisco's setup has non-negative so Dijkstra is fine). Bring this up only as a fallback if the interviewer asks 'what about negative weights?'

2. Dijkstra with binary heap (optimal)

Use a min-heap keyed on tentative distance. Pop the closest unvisited node, relax its outgoing edges, repeat.

Time
O(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;
  // Simple binary min-heap
  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]) {
      const nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        heap.push([nd, v]);
      }
    }
  }
  let max = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    max = Math.max(max, dist[i]);
  }
  return max;
}

Tradeoff: The sort-then-shift here is O(n log n) per pop and not a real heap — production code would use a proper PriorityQueue. Cisco interviewers know JS doesn't ship a heap; saying 'I'd swap this for a binary heap with O(log n) decrease-key in production' earns full marks.

Cisco-specific tips

Cisco is a NETWORKING company. Frame this problem in their language out loud: 'This is single-source shortest path on a weighted directed graph, which is exactly Dijkstra. The answer is the maximum of the shortest-path distances — if any distance is Infinity, some node is unreachable and we return -1.' Acknowledge JavaScript's missing heap explicitly — the interviewer will respect the awareness that real Cisco services would run this in C++ with std::priority_queue.

Common mistakes

  • Forgetting that the answer is the MAX of all distances (the slowest node to receive the signal), not the sum.
  • Returning the wrong sentinel — must check 'any distance still Infinity → return -1' before taking the max.
  • Using Bellman-Ford when the graph has 6000 edges and 100 nodes — O(V*E) is 600,000 ops, fine for the constraints but a flag to the interviewer that you don't know Dijkstra.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • Cheapest Flights Within K Stops (LC 787) — Dijkstra variant with hop-limit constraint, or Bellman-Ford bounded to K+1 relaxations.
  • Network Connectivity / minimum spanning tree (LC 1135 — Prim's or Kruskal's).
  • What if edge weights could be negative? (Bellman-Ford handles that, Dijkstra does not.)
  • What if you also need to return the PATH, not just the distance? (Track predecessor pointers during relaxation.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is JavaScript such a poor fit for Dijkstra?

JavaScript's standard library has no priority queue. You either fake it with a sorted array (the version above, O(n) per op) or hand-roll a binary heap. Cisco interviewers know this and just want to hear you acknowledge it — 'in production this would be a proper heap with O(log n) decrease-key.'

Does Cisco accept Bellman-Ford as the primary solution?

Only if you ALSO say Dijkstra is the right answer and you'd use Bellman-Ford only for negative weights. Going straight to Bellman-Ford without naming Dijkstra is a red flag at Cisco specifically because shortest-path-on-positive-weights is their bread and butter.

Is this a Cisco-specific question or a general one?

It's a real LeetCode problem (#743) asked at many companies, but Cisco asks it at unusually high frequency because the problem statement reads like a Cisco product spec. The framing — signal propagation through a network — is the most on-brand any LC problem gets.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Network Delay Time and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →