Network Delay Time

MEDIUM✓ CHIP-TIMEDLC #743 — FULL STATEMENT ↗

The drill: A signal fires from one node across a directed, weighted network. Find how long it takes for every node to receive it — or report that some node never will.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A directed network of nodes and weighted wires arrives, along with the node where a signal originates. Every wire carries a positive travel time in one direction only.

The signal spreads outward, and each node's arrival time is the length of its fastest route from the source. Because the spread happens in parallel across every route, the network isn't 'done' until its slowest node has heard the signal.

The answer is that slowest arrival time across every node. If some node can never be reached at all from the source, the whole network never finishes, and that failure needs to be signaled distinctly.

EX 01

times = [[1, 2, 5]] · n = 2 · k = 1

→ 5

SINGLE EDGE, ONE HOP

EX 02

times = [[1, 2, 5]] · n = 2 · k = 2

→ -1

NO PATH BACK — UNREACHABLE

EX 03

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

→ 4

DIRECT EDGE BEATEN BY THE TWO-HOP RELAY

nodes and wires can number up to roughly a hundred and a few thousand
wire travel times are positive integers
wires are one-directional; a return path is a separate wire
unreachable nodes make the whole answer -1

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The answer isn't the total wire length used — it's how long the SLOWEST node takes to hear the signal, since every node gets it in parallel along its own shortest route.

HINT 2 THE STRUCTURE

This is single-source shortest paths on a directed graph with positive weights. The relay chase is: what's the fastest confirmed arrival time at each node, expanding outward from the source?

HINT 3 ONE STEP FROM THE ANSWER

Dijkstra from k with a min-heap: pop the closest unfinalized node, lock in its distance, relax its outgoing edges. The answer is the max over all locked-in distances — or −1 if fewer than n nodes ever lock in.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SIGNAL RELAYPATTERN · DIJKSTRA WITH A HEAPtimes: 1→2(1) 2→3(2) 1→3(4) 3→4(1) · n=4 · k=1

(0, 1)

STEP 1

Dijkstra from node 1: a min-heap always pops the currently-closest unfinalized node next.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/network-delay-time.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        dist = {}
        pq = [(0, k)]
        while pq:
            d, u = heapq.heappop(pq)
            if u in dist:
                continue
            dist[u] = d
            for v, w in graph[u]:
                if v not in dist:
                    heapq.heappush(pq, (d + w, v))
        if len(dist) != n:
            return -1
        return max(dist.values())

TIME O(E·LOG V)SPACE O(V + E)PYTHON · RACE PACE · 18 LN

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        INF = float('inf')
        dist = [INF] * (n + 1)
        dist[k] = 0
        for _ in range(n - 1):
            updated = False
            for u, v, w in times:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    updated = True
            if not updated:
                break
        mx = max(dist[1:n + 1])
        return mx if mx < INF else -1

TIME O(V·E)SPACE O(V)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] t : times) {
            graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[] { t[1], t[2] });
        }
        Map<Integer, Integer> dist = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[] { 0, k });
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (dist.containsKey(u)) continue;
            dist.put(u, d);
            for (int[] edge : graph.getOrDefault(u, Collections.emptyList())) {
                int v = edge[0], w = edge[1];
                if (!dist.containsKey(v)) {
                    pq.offer(new int[] { d + w, v });
                }
            }
        }
        if (dist.size() != n) return -1;
        return Collections.max(dist.values());
    }
}

TIME O(E·LOG V)SPACE O(V + E)JAVA · RACE PACE · 25 LN

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (int[] t : times) {
                int u = t[0], v = t[1], w = t[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }
        int mx = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            mx = Math.max(mx, dist[v]);
        }
        return mx;
    }
}

TIME O(V·E)SPACE O(V)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED