#743 Network Delay Time

frequently reported atNetflix Google Amazon

the problem

In plain words

A signal starts at node k in a directed, weighted network of n nodes (labelled 1..n). times[i] = [u, v, w] means it takes w time to travel from u to v. Return how long until every node has the signal, or -1 if some node never gets it.

in times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

out 2

Node 4 is the last to hear it: 2→3→4 takes 2.

in times = [[1,2,1]], n = 2, k = 1

out 1

in times = [[1,2,1]], n = 2, k = 2

out -1

From node 2 the signal can't reach node 1.

1 ≤ k ≤ n ≤ 100
1 ≤ times.length ≤ 6000
0 ≤ w ≤ 100
All (u, v) pairs are unique

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternDijkstra

Every node hears the signal at its shortest-path distance from k. The answer is the largest of those distances — so run single-source shortest paths and take the max.

solutions

From brute force to optimal

Relax every edge up to n − 1 times, then take the max distance.

dist[k] = 0, everything else ∞.
Repeat n − 1 times: relax all edges (stop early if nothing changes).
Any ∞ → -1, else return the max.

timeO(n · E)

n − 1 rounds over all E edges.

spaceO(n)

Only the dist array; the edge list is the input.

javajava.util.*

1class Solution {2    public int networkDelayTime(int[][] times, int n, int k) {3        int[] dist = new int[n + 1];4        Arrays.fill(dist, Integer.MAX_VALUE);5        dist[k] = 0;6        for (int round = 1; round <= n - 1; round++) {      // n − 1 rounds are always enough7            boolean changed = false;8            for (int[] t : times) {9                int u = t[0], v = t[1], w = t[2];10                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {11                    dist[v] = dist[u] + w;12                    changed = true;13                }14            }15            if (!changed) break;16        }17        int worst = 0;18        for (int v = 1; v <= n; v++) {19            if (dist[v] == Integer.MAX_VALUE) return -1;20            worst = Math.max(worst, dist[v]);21        }22        return worst;23    }24}

Weights are non-negative, so poll the closest node each time; its distance is final.

Build an adjacency list (nodes are 1-indexed → size n + 1).
Push {0, k}. Poll the smallest; skip stale entries.
Relax outgoing edges, pushing improved distances.
Return max(dist[1..n]), or -1 if any node is still ∞.

timeO((n + E) log n)

Each edge can push once; each push/poll is O(log E) = O(log n).

spaceO(n + E)

Adjacency list plus up to E heap entries.

javajava.util.*

1class Solution {2    public int networkDelayTime(int[][] times, int n, int k) {3        List<List<int[]>> adj = new ArrayList<>();4        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); // nodes are 1..n5        for (int[] t : times) adj.get(t[0]).add(new int[] {t[1], t[2]});6 7        int[] dist = new int[n + 1];8        Arrays.fill(dist, Integer.MAX_VALUE);9        dist[k] = 0;10        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));11        pq.offer(new int[] {0, k});12        while (!pq.isEmpty()) {13            int[] top = pq.poll();14            int d = top[0], u = top[1];15            if (d > dist[u]) continue;16            for (int[] next : adj.get(u)) {17                int v = next[0], w = next[1];18                if (d + w < dist[v]) {19                    dist[v] = d + w;20                    pq.offer(new int[] {dist[v], v});21                }22            }23        }24        int worst = 0;25        for (int v = 1; v <= n; v++) {26            if (dist[v] == Integer.MAX_VALUE) return -1;     // someone never hears the signal27            worst = Math.max(worst, dist[v]);28        }29        return worst;30    }31}

sim

Dry run (0-indexed nodes)

loading simulation…

javajava.util.*

1class Solution {2    public int networkDelayTime(int[][] times, int n, int k) {3        List<List<int[]>> adj = new ArrayList<>();4        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); // nodes are 1..n5        for (int[] t : times) adj.get(t[0]).add(new int[] {t[1], t[2]});6 7        int[] dist = new int[n + 1];8        Arrays.fill(dist, Integer.MAX_VALUE);9        dist[k] = 0;10        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));11        pq.offer(new int[] {0, k});12        while (!pq.isEmpty()) {13            int[] top = pq.poll();14            int d = top[0], u = top[1];15            if (d > dist[u]) continue;16            for (int[] next : adj.get(u)) {17                int v = next[0], w = next[1];18                if (d + w < dist[v]) {19                    dist[v] = d + w;20                    pq.offer(new int[] {dist[v], v});21                }22            }23        }24        int worst = 0;25        for (int v = 1; v <= n; v++) {26            if (dist[v] == Integer.MAX_VALUE) return -1;     // someone never hears the signal27            worst = Math.max(worst, dist[v]);28        }29        return worst;30    }31}

in the room

How to say it in the interview

talk track

Restate: "time for everyone to hear = the farthest node's shortest distance."
Check weights: non-negative → Dijkstra. Mention Bellman–Ford if they ask about negative times.
Call out the 1-indexing and the unreachable case before coding.

traps

Returning the sum of distances instead of the max.
Allocating n slots for 1-indexed nodes — you need n + 1.

what they ask next

Follow-ups

What if n were tiny but the graph dense?

The O(n²) array Dijkstra avoids heap overhead and is optimal for E ≈ n².

Return the actual slowest route?

Keep parent[v] on every improvement, find the farthest node, and walk back.

before you submit

Edge cases to test

Some node is never reached → -1 (check every dist, not only the maximum).
Zero-weight edges (w can be 0) — fine for Dijkstra.
The direct edge is slower than a longer route: 1→2 costs 5, but 1→3→2 costs 2.
k has no outgoing edges and n > 1 → -1.

practise next