Network Delay Time

Medium Problem 112 of 151 Java and Python

Problem

A network has n nodes labelled 1 to n. times[i] = [u, v, w] means a signal takes w time to travel from u to v (directed).

A signal is sent from node k. Return the time it takes for all nodes to receive it, or -1 if some node never does.

Example 1

Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
Output: 2
Why: Node 4 is reached last, at time 2.

Example 2

Input: times = [[1, 2, 1]], n = 2, k = 2
Output: -1
Why: Node 1 cannot be reached from 2.

Constraints

1 ≤ k ≤ n ≤ 100
1 ≤ times.length ≤ 6000
0 ≤ w ≤ 100

Explanation

Each node receives the signal at its shortest-path distance from k; the answer is the largest of those distances.

With non-negative weights, Dijkstra's algorithm finds all shortest distances: always settle the unsettled node with the smallest known distance (using a min-heap), then relax its outgoing edges.

Approach 1 · Naive

Bellman-Ford

Time O(n · E)
Space O(n)

Relax every edge n - 1 times. After that, every shortest distance is final.

dist[k] = 0, others infinity.
Repeat n - 1 times: for each edge (u, v, w), dist[v] = min(dist[v], dist[u] + w).
Return the maximum distance, or -1 if any is infinity.

Java

import java.util.*;

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 round = 1; round < n; round++) {
            for (int[] t : times) {
                if (dist[t[0]] != Integer.MAX_VALUE && dist[t[0]] + t[2] < dist[t[1]]) {
                    dist[t[1]] = dist[t[0]] + t[2];
                }
            }
        }
        int worst = 0;
        for (int i = 1; i <= n; i++) {
            worst = Math.max(worst, dist[i]);
        }
        return worst == Integer.MAX_VALUE ? -1 : worst;
    }
}

Python

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dist = [float("inf")] * (n + 1)
        dist[k] = 0
        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
        worst = max(dist[1:])
        return -1 if worst == float("inf") else worst

Approach 2 · Optimal

Dijkstra with a min-heap

Time O(E log E)
Space O(n + E)

Pop the closest unsettled node from a heap, settle it, and push its neighbours with improved distances.

Build an adjacency list. Push (0, k).
Pop (d, u); skip if u is already settled; otherwise settle it with distance d.
For each edge u → v with weight w, push (d + w, v) if v is not settled.
If all n nodes are settled, return the largest distance; else -1.

Java

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] t : times) {
            graph.get(t[0]).add(new int[] { t[1], t[2] });
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[] { 0, k });
        boolean[] settled = new boolean[n + 1];
        int count = 0;
        int time = 0;
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0];
            int u = top[1];
            if (settled[u]) {
                continue;
            }
            settled[u] = true;
            count++;
            time = d;
            for (int[] edge : graph.get(u)) {
                if (!settled[edge[0]]) {
                    heap.offer(new int[] { d + edge[1], edge[0] });
                }
            }
        }
        return count == n ? time : -1;
    }
}

Python

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))
        heap = [(0, k)]
        settled = {}
        while heap:
            d, u = heapq.heappop(heap)
            if u in settled:
                continue
            settled[u] = d
            for v, w in graph[u]:
                if v not in settled:
                    heapq.heappush(heap, (d + w, v))
        return max(settled.values()) if len(settled) == n else -1

Complexity compared

Approach	Time	Space
Naive Bellman-Ford	O(n · E)	O(n)
Optimal Dijkstra with a min-heap	O(E log E)	O(n + E)

Key takeaways

Dijkstra needs non-negative weights. With negative weights, use Bellman-Ford.
Nodes are popped in order of distance, so the last node settled has the largest distance.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem