How do you solve Network Delay Time?

Build an adjacency list from the input edges for efficient neighbor lookup. Use a min-heap initialized with the starting node k at distance 0. Repeatedly pop the node with the smallest tentative distance, skip if already visited, and update the maximum time seen. For each neighbor, if unvisited, push the cumulative distance into the heap. After processing, if all nodes are visited, return the maximum distance; otherwise, return -1.

What pattern does Network Delay Time use?

The Pattern: Dijkstra's Algorithm (Single-Source Shortest Path) The Heuristic: Always expand the closest unvisited node next using a min-heap to guarantee that once a node is visited, its shortest path is finalized, enabling efficient and correct shortest path computation.

Network Delay Time — Dijkstra's Algorithm

Q: What is the time complexity of Network Delay Time?

O(E log V). Each edge is processed at most once when its source node is popped from the heap, and each heap operation takes O(log V) time, where V is the number of nodes and E is the number of edges.

Problem

Given a list of travel times as directed edges times where times[i] = (u, v, w) represents the time w to travel from node u to node v, and given the number of nodes n and a starting node k, return the time it takes for all nodes to receive the signal sent from node k. If it is impossible for all nodes to receive the signal, return -1.

1 ≤ k ≤ n ≤ 100
1 ≤ times.length ≤ 6000
times[i].length == 3
1 ≤ u, v ≤ n
u != v
0 ≤ w ≤ 100
All pairs (u, v) are unique.

Example

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

Output: 2

Starting from node 2, the signal reaches node 1 in 1 unit of time and node 3 in 1 unit of time. From node 3, the signal reaches node 4 in 1 additional unit of time. The longest time among all nodes to receive the signal is 2, which is the answer.

Approach

Straightforward Solution

A brute-force approach would attempt to explore all paths from k to every node, which is computationally expensive and inefficient, especially with cycles and multiple paths.

Core Observation

The problem reduces to finding the shortest path from a single source node k to all other nodes in a weighted directed graph, where edge weights represent travel times.

Path to Optimal

Preview

Recognizing the problem as a shortest path problem on a weighted graph suggests using Dijkstra's algorithm. The key insight is to use a priority queue (min-heap) to always explore the next closest node, ensuring that once a node is visited, the shortest path to it is finalized…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an adjacency list from the input edges for efficient neighbor lookup. Use a min-heap initialized with the starting node k at distance 0…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(E log V)

Each edge is processed at most once when its source node is popped from the heap, and each heap operation takes O(log V) time, where V is the number of nodes and E is the number of edges.

Space

O(V + E)

The adjacency list stores all edges (O(E)), and the heap and visited set store nodes (O(V)). This space is necessary to represent the graph and track visited nodes.

Solution

Python

1import collections
2import heapq
3
4class Solution:
  def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
      edges = collections.defaultdict(list)
      for u, v, w in times:
          edges[u].append((v, w))
      
      min_heap = [(0, k)]
      visit = set()
      t = 0
      while min_heap:
          w1, n1 = heapq.heappop(min_heap)
          if n1 in visit:
              continue
          visit.add(n1)
          t = max(t, w1)
          
          for n2, w2 in edges[n1]:
              if n2 not in visit:
                  heapq.heappush(min_heap, (w1 + w2, n2))
      
      return t if len(visit) == n else -1

Step-by-Step Solution

1

Build the Graph as an Adjacency List for Efficient Neighbor Lookup

6edges = collections.defaultdict(list)
7for u, v, w in times:
8    edges[u].append((v, w))

Objective

To transform the edge list into a structure that allows quick access to neighbors and their travel times.

Key Insight

An adjacency list maps each node to a list of its outgoing edges, enabling O(1) average-time access to neighbors during traversal. This structure is essential for efficient graph algorithms like Dijkstra's, avoiding repeated scanning of the entire edge list.

Interview Quick-Check

Core Logic

Using a defaultdict of lists to store edges allows efficient iteration over neighbors during the shortest path search.

Common Pitfalls & Bugs

Forgetting to build the adjacency list or using an inefficient data structure can lead to slower neighbor lookups and increased time complexity.

2

Initialize Min-Heap and Visited Set to Track Exploration State

To prepare the data structures that manage the order of node exploration and prevent revisiting nodes.

3

Process Nodes in Order of Increasing Distance and Update Maximum Delay

To iteratively explore the graph, finalizing shortest paths and tracking the longest time needed for the signal to reach any node.

4

Push Neighboring Nodes into the Heap with Updated Distances

To explore all reachable neighbors by adding them to the heap with their cumulative distances from the source.

5

Return the Maximum Delay if All Nodes Are Visited, Otherwise Return -1

To determine if the signal reached all nodes and return the appropriate result.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 14 Critical

w1, n1 = heapq.heappop(min_heap)

Pop the node with the smallest tentative distance from the heap.

Extracting the closest unvisited node is the core operation of Dijkstra's algorithm, guaranteeing that the shortest path to this node is finalized.

Line 24 Critical

return t if len(visit) == n else -1

Return the maximum delay if all nodes are visited; otherwise, return -1.

This conditional return correctly handles disconnected graphs by returning -1 when some nodes are unreachable, and otherwise returns the longest shortest path as the answer.

Line 10 Critical

min_heap = [(0, k)]

Initialize a min-heap with a tuple representing the starting node k at distance 0.

The min-heap prioritizes nodes by their current shortest known distance from the source, enabling Dijkstra's algorithm to explore nodes in order of increasing distance.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does Dijkstra's algorithm guarantee that the first time a node is visited, the shortest path to it has been found?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Network Delay Time from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Network Delay Time drill

or drill a free problem

1	`import collections`
2	`import heapq`
3
4	`class Solution:`
5	`def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:`
6	`edges = collections.defaultdict(list)`
7	`for u, v, w in times:`
8	`edges[u].append((v, w))`
9
10	`min_heap = [(0, k)]`
11	`visit = set()`
12	`t = 0`
13	`while min_heap:`
14	`w1, n1 = heapq.heappop(min_heap)`
15	`if n1 in visit:`
16	`continue`
17	`visit.add(n1)`
18	`t = max(t, w1)`
19
20	`for n2, w2 in edges[n1]:`
21	`if n2 not in visit:`
22	`heapq.heappush(min_heap, (w1 + w2, n2))`
23
24	`return t if len(visit) == n else -1`