MediumDepth-First SearchBreadth-First SearchGraphHeapShortest PathDijkstra's AlgorithmUpdated Sep 2026

743. Network Delay Time

Asked at Netflix, NVIDIA

Difficulty

Medium

Time

O(E log V)

Space

O(V + E)

Pattern

Depth-First Search

Companies

2

Problem

You have a network of n nodes, numbered 1 to n. The list times describes directed connections: each entry [u, v, w] means a signal can travel from node u to node v and takes w time units.

A signal is sent from node k at time 0. It spreads along the connections, and a node receives the signal as soon as the fastest path from k reaches it. Return the minimum time when every node has received the signal. If some node can never be reached from k, return -1.

In other words, find the shortest travel time from k to each node, then take the largest of those times. The last node to hear the signal decides the answer.

Signal spreading from node 2

start at k = 2, time 02 → 1 costs 12 → 3 costs 13 → 4 costs 1, total 2Follow the edges and add up the weights
The signal reaches nodes 1 and 3 at time 1, then node 4 at time 2 — the last arrival is the answer.

Constraints

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

Examples

Example 1
Inputtimes = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output2
WhyFrom node 2: node 1 takes 1, node 3 takes 1, and node 4 takes 1+1=2 via node 3. The slowest node is 4 at time 2, so the whole network is covered at time 2.
Example 2
Inputtimes = [[1,2,1]], n = 2, k = 1
Output1
WhyNode 1 is the source (time 0) and node 2 is reached in 1 unit. The maximum of {0, 1} is 1.
Example 3
Inputtimes = [[1,2,1]], n = 2, k = 2
Output-1
WhyThe only edge goes from 1 to 2, so starting at node 2 the signal can never reach node 1. Not all nodes are covered, so the answer is -1.

Asked At

2 companies
CompanyDifficulty
NetflixMediumView all Netflix questions →
NVIDIAMediumView all NVIDIA questions →

How to Think About It

1

Build an adjacency list representation of the weighted directed graph

2

Use Dijkstra's algorithm with a min-heap to greedily find shortest paths

3

Initialize distances to infinity except source which is 0

4

Process nodes in order of increasing distance from source

5

The answer is the maximum distance among all reachable nodes

Optimal Approach

Model the network as a weighted directed graph using an adjacency list. Apply Dijkstra's algorithm starting from the source node. Use a min-heap (priority queue) to always process the node with the smallest known distance next. For each node popped from the heap, relax all its outgoing edges: if the distance to a neighbor through the current node is shorter than the known distance, update it and push to the heap. After processing, the answer is the maximum distance across all nodes. If any node remains at infinity, return -1.

Dijkstra with a min-heap

dist1234∞0∞∞Start: source node 2 has distance 0, all others areunknowndist1234101∞Pop node 2, relax its edges: nodes 1 and 3 getdistance 1dist12341012Pop node 3, relax its edge: node 4 gets distance 1 + 1= 2answer = max(dist) = 2if any dist is ∞ → return -1
Always settle the closest unsettled node first, then relax its outgoing edges.
ComplexityTime O(E log V)Space O(V + E)Each edge can push one entry into the heap, and each heap operation costs O(log V); V is the node count and E the edge count.

What Trips People Up in Real Interviews

1

Confirm the graph is directed and edges have non-negative weights

2

Ask if there are negative edge weights (would need Bellman-Ford instead)

3

Clarify that the answer is the max of all shortest paths, not the sum

4

Mention BFS works for unweighted graphs but Dijkstra is needed here

5

Discuss time complexity: O((V+E) log V) with a binary heap

Solution Code

O(E log V) time
import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = {}
        min_heap = [(0, k)]

        while min_heap:
            d, node = heapq.heappop(min_heap)
            if node in dist:
                continue
            dist[node] = d
            for neighbor, weight in graph[node]:
                if neighbor not in dist:
                    heapq.heappush(min_heap, (d + weight, neighbor))

        return max(dist.values()) if len(dist) == n else -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Network Delay Time problem?

Given a network of N nodes with weighted directed edges and a source node, find the time it takes for a signal to reach all nodes. Return the minimum time needed, or -1 if some nodes are unreachable. This is the classic single-source shortest path problem on a weighted graph.

How do you solve Network Delay Time?

The optimal approach runs in O(E log V) time and O(V + E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Network Delay Time?

Network Delay Time is asked at Netflix, NVIDIA. It is a medium difficulty problem.

What are common mistakes on Network Delay Time?
  • Confirm the graph is directed and edges have non-negative weights
  • Ask if there are negative edge weights (would need Bellman-Ford instead)
  • Clarify that the answer is the max of all shortest paths, not the sum
  • Mention BFS works for unweighted graphs but Dijkstra is needed here
  • Discuss time complexity: O((V+E) log V) with a binary heap