How do you approach Network Delay Time?

This is single-source shortest path on a weighted directed graph - Dijkstra's algorithm.

What are common mistakes on Network Delay Time?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Network Delay Time

MediumAlgorithms

Description

You are given a network of `n` nodes labeled `1` to `n` and a list `times` where `times[i] = [u, v, w]` means a signal travels from `u` to `v` in `w` time. Send a signal from node `k`. Return the time it takes for **all** nodes to receive the signal, or `-1` if some node is unreachable.

Example 1

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

Output: 2

Explanation: The farthest node (4) receives the signal at time 2.

Example 2

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

Output: -1

Explanation: Node 1 is unreachable from 2.

Constraints

- 1 <= k <= n <= 100 - 1 <= times.length <= 6000 - All (u, v) pairs are unique

Network Delay Time: approach, complexity and pitfalls

A medium graphs problem, graded against 4 test cases (2 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

More Graphsproblems →

If you are stuck

Show the 3-step hint ladder

This is single-source shortest path on a weighted directed graph - Dijkstra's algorithm.
The answer is the maximum shortest-path distance over all nodes (or -1 if any is infinite).
No heap module is available - select the unvisited node with the smallest distance by scanning.

The optimal approach

Show the approach: The approach

Dijkstra (O(V²) selection variant). Maintain a distance array seeded with `dist[k] = 0`. Repeatedly pick the unvisited node with the smallest distance, finalize it, and relax its outgoing edges. The answer is the maximum finalized distance, or -1 if any node stays at infinity.

Time: O(V² + E). Space: O(V + E).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.