Log inSign up
mediumLeetCodeNot Started

Network Delay Time

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

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 the source to the 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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify Single-Source Shortest Path (SSSP) broadcast modeling in real-world network routing.
  • Implement Dijkstra's Algorithm using an adjacency list and min-heap (PriorityQueue).
  • Handle 1-based indexing and unreachable node validation correctly.
  • Compare Bellman-Ford vs. Dijkstra for non-negative edge weight graphs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a question describes a signal, virus, rumor, or wave broadcasting simultaneously from a source with positive traversal delays, model it as finding the shortest path to all vertices. The overall completion time is the maximum of these shortest paths.

1. DFS / Exhaustive Path Search

Intuition

Explore all possible simple directed paths from source k to every other node using Depth-First Search. Maintain an array dist where dist[v] stores the minimum time found so far to reach node v. If a newly explored path reaches v in less time, update dist[v] and recursively explore neighbors. Due to cycles and alternate paths, an unpruned DFS may explore exponentially many paths.

Algorithm

  1. Construct an adjacency list for the directed edges.
  2. Initialize dist array of size n + 1 with infinity, set dist[k] = 0.
  3. Define dfs(u, current_time):
  4. If current_time >= dist[u], return (pruning).
  5. dist[u] = current_time.
  6. For each outgoing edge (v, weight) from u:
  7. dfs(v, current_time + weight).
  8. Run dfs(k, 0).
  9. Find the maximum value among dist[1..n]. If any node has infinity, return -1; otherwise return max time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6void dfs(int u, int timeSoFar, const std::vector<std::vector<std::pair<int, int>>>& adj, std::vector<int>& dist) {
7 if (timeSoFar >= dist[u]) return;
8 dist[u] = timeSoFar;
9 for (const auto& [v, w] : adj[u]) {
10 dfs(v, timeSoFar + w, adj, dist);
11 }
12}
13
14int networkDelayTimeDFS(std::vector<std::vector<int>>& times, int n, int k) {
15 std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
16 for (const auto& t : times) {
17 adj[t[0]].push_back({t[1], t[2]});
18 }
19
20 std::vector<int> dist(n + 1, INT_MAX);
21 dfs(k, 0, adj, dist);
22
23 int maxTime = 0;
24 for (int i = 1; i <= n; ++i) {
25 if (dist[i] == INT_MAX) return -1;
26 maxTime = std::max(maxTime, dist[i]);
27 }
28 return maxTime;
29}
30
31int main() {
32 std::vector<std::vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
33 std::cout << "Delay Time DFS: " << networkDelayTimeDFS(times, 4, 2) << std::endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(V!) in the worst-case on dense DAGs/cyclic graphs where multiple paths of varying lengths are explored repeatedly.
  • Space complexity: O(V) for the recursion stack and distance tracking array.

2. Bellman-Ford Algorithm

Intuition

Relax all directed edges n - 1 times. In each round of relaxation, if dist[u] != \infty and dist[u] + w < dist[v], update dist[v] = dist[u] + w. Because the shortest path in a graph with n vertices contains at most n - 1 edges, n - 1 rounds are guaranteed to find the true shortest path to all reachable nodes without needing a priority queue.

Algorithm

  1. Initialize dist array of size n + 1 with infinity, set dist[k] = 0.
  2. Loop n - 1 times:
  3. Maintain a boolean flag updated = false.
  4. For each directed edge (u, v, w) in times:
  5. If dist[u] != inf and dist[u] + w < dist[v]:
  6. dist[v] = dist[u] + w
  7. updated = true
  8. If not updated, break early.
  9. Find the maximum value among dist[1..n]. If any node is infinity, return -1; otherwise return max time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6int networkDelayTimeBellmanFord(std::vector<std::vector<int>>& times, int n, int k) {
7 std::vector<int> dist(n + 1, INT_MAX);
8 dist[k] = 0;
9
10 for (int i = 1; i <= n - 1; ++i) {
11 bool updated = false;
12 for (const auto& edge : times) {
13 int u = edge[0], v = edge[1], w = edge[2];
14 if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
15 dist[v] = dist[u] + w;
16 updated = true;
17 }
18 }
19 if (!updated) break;
20 }
21
22 int maxTime = 0;
23 for (int i = 1; i <= n; ++i) {
24 if (dist[i] == INT_MAX) return -1;
25 maxTime = std::max(maxTime, dist[i]);
26 }
27 return maxTime;
28}
29
30int main() {
31 std::vector<std::vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
32 std::cout << "Delay Time Bellman-Ford: " << networkDelayTimeBellmanFord(times, 4, 2) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(V * E) where V is n and E is times.length. For dense graphs with n = 100, E = 6000, operations = 6 * 10^5, well within time limits.
  • Space complexity: O(V) auxiliary space for the distance array.

3. Dijkstra's Algorithm with Min-Heap

Intuition

Because edge weights represent physical travel times and are non-negative (w_i >= 0), Dijkstra's algorithm is optimal. Using a priority queue ordered by elapsed time, we greedily finalize the node with the currently shortest distance. When node u is popped, its distance is finalized; we relax all outgoing edges (u, v) and push updated distances into the min-heap.

Algorithm

  1. Build an adjacency list adj where adj[u] contains pairs (v, weight).
  2. Initialize dist array of size n + 1 with infinity, set dist[k] = 0.
  3. Push (0, k) into min-heap (ordered by travel time).
  4. While min-heap is not empty:
  5. Pop (d, u). If d > dist[u], continue (stale entry).
  6. For each neighbor (v, weight) in adj[u]:
  7. If dist[u] + weight < dist[v]:
  8. dist[v] = dist[u] + weight
  9. Push (dist[v], v) into min-heap.
  10. Compute ans = max(dist[1..n]).
  11. Return ans == infinity ? -1 : ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5#include <climits>
6
7int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
8 std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
9 for (const auto& t : times) {
10 adj[t[0]].push_back({t[1], t[2]});
11 }
12
13 std::vector<int> dist(n + 1, INT_MAX);
14 // pair: (distance, node)
15 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
16
17 dist[k] = 0;
18 pq.push({0, k});
19
20 while (!pq.empty()) {
21 auto [d, u] = pq.top();
22 pq.pop();
23
24 if (d > dist[u]) continue;
25
26 for (const auto& [v, w] : adj[u]) {
27 if (dist[u] + w < dist[v]) {
28 dist[v] = dist[u] + w;
29 pq.push({dist[v], v});
30 }
31 }
32 }
33
34 int maxTime = 0;
35 for (int i = 1; i <= n; ++i) {
36 if (dist[i] == INT_MAX) return -1;
37 maxTime = std::max(maxTime, dist[i]);
38 }
39 return maxTime;
40}
41
42int main() {
43 std::vector<std::vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
44 std::cout << "Optimal Network Delay Time: " << networkDelayTime(times, 4, 2) << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(E log V) where E is the number of edges and V is n. Each edge is relaxed and pushed to heap at most once.
  • Space complexity: O(V + E) for the adjacency list and priority queue.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS Exhaustive SearchO(V!)O(V)Simple recursive backtracking logic.Exponential runtime; repeatedly explores subpaths without greedy pruning.
2.Bellman-FordO(V * E)O(V)Very clean code with no priority queue; handles negative edge weights if present.Slower than Dijkstra when edge weights are all non-negative.
3.Dijkstra's with Min-HeapOptimalO(E log V)O(V + E)Asymptotically optimal for non-negative weights; processes each vertex greedily.Requires min-heap / priority queue data structure.

Common Pitfalls & Crucial Edge Cases

Forgetting that nodes are 1-indexed (1 to n).

Allocate arrays of size n + 1 and iterate from 1 to n to avoid off-by-one errors.

Treating directed edges as undirected.

Edge (u, v, w) is directed from u to v. Only add v to adj[u], do not add u to adj[v].

Omitting the stale entry check `if (d > dist[u]) continue;` in Dijkstra.

Min-heap can contain multiple entries for the same node; skipping obsolete entries prevents redundant neighbor relaxations.

Crucial Edge Cases to Validate:

  • k is an isolated vertex with no outgoing edges and n > 1 — Other nodes remain at infinity, algorithm correctly returns -1.
  • n = 1 — Single node is the source k; loop finds max(dist[1]) = 0 and returns 0.
  • Disconnected graph with multiple components — Any unvisited component keeps distance infinity; algorithm returns -1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether edge weights can be negative. If non-negative, state that Dijkstra's is optimal with O(E log V) time.
  2. Highlight the parallel broadcast nature: 'Signals propagate in parallel, so total time is max(shortest paths).'
  3. Point out the 1-indexed node numbers and ensure safe allocation of size n + 1.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the final answer take max(dist[1..n]) instead of the sum of dist[1..n]?

2.What should be returned if one or more nodes are unreachable from source k?

3.Can Dijkstra's algorithm be used if some travel times were negative?

Back to DSA Sheet