Graphs/Network Delay TimeMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Network Delay Time

Graphs·Medium

There are n network nodes labeled 1 to n. You are given a list of travel times as directed edges times[i] = [u, v, w] where u is the source, v the target, and w the travel time. Given a source node k, return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

Use Dijkstra's algorithm: run a single-source shortest-path from k. The answer is the maximum of all shortest distances (since every node must have received the signal). If any node remains unreachable, return -1.

Examples

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

Output: 2

Node 2 can reach nodes 1 (cost 1), 3 (cost 1), and 4 (cost 2). The last node to receive is node 4 at time 2.

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

Output: 1

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

Output: -1

Node 2 has no outgoing edges so node 1 is unreachable.

Constraints

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

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Graphs
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.