Sweaty Imposter

Network Delay Time

MediumGraph BFS/DFSNeetCode 150MidOpen on LeetCodeUpdated

A network has n nodes labeled 1 to n. You're given times, a list of directed edges [u, v, w] meaning a signal sent from u reaches v after w units of time. A signal starts at node k. Return how long it takes until every node has received it, or -1 if some node never does.

Examples

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

1234

Node 3 hears at time 1. Node 2 hears at time 3 through node 3, earlier than the direct edge's 4. Node 4 then hears at time 4, the last arrival.

times = [[1,2,5],[2,3,2]], n = 3, k = 3 returns -1

Node 3 has no outgoing edges, so nodes 1 and 2 never receive the signal.

times = [[2,1,6],[2,3,2],[3,1,1]], n = 3, k = 2 returns 3

Node 1 hears at time 3 through node 3, beating the direct edge's 6.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • 1 <= w <= 100
  • No two edges share the same ordered pair (u, v).

Hints

Hint 1

When does the last node receive the signal, in terms of shortest paths?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Every node hears the signal at its shortest-path distance from k, so the answer is the largest of those distances. With non-negative weights, Dijkstra's algorithm finds them: keep a min-heap of (time, node), pop the earliest, skip it if the node is already settled, and otherwise settle it and push each neighbor at time + w. If fewer than n nodes are settled when the heap empties, return -1; otherwise return the last settled time, which is the largest. O(E log E) time and O(n + E) space.

Time

O(E log E)

Space

O(n + E)

Pitfall

Using plain BFS and taking the first time a node is reached. BFS minimizes the number of edges, and a path with more edges can be faster, as with node 2 in the first example.

Solutions

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) -> a[0] - b[0]);
        heap.offer(new int[] {0, k});
        boolean[] settled = new boolean[n + 1];
        int count = 0, last = 0;
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int time = top[0], u = top[1];
            if (settled[u]) continue;
            settled[u] = true;
            count++;
            last = time;
            for (int[] edge : graph.get(u)) {
                if (!settled[edge[0]]) heap.offer(new int[] {time + edge[1], edge[0]});
            }
        }
        return count == n ? last : -1;
    }
}
Drill This