How Long Until Every Server Hears the Broadcast
Solve this ProblemA message is broadcast from one server in a network of servers joined by one-way links, each with a positive delay, given as an n × n matrix. Every server forwards the message immediately along all of its links. Find when the last server receives it, or -1 if some server is never reached.
This is a single-source shortest path problem; the answer is the largest of the shortest arrival times.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 servers numbered 0 … n-1; links is an n × n matrix: links[u][v] = 0 means no direct link from u to v, links[u][v] = t (1 ≤ t ≤ 20) means a one-way link that delivers a message from u to v in t time units - ◆
links[u][u] = 0; every server that receives the message forwards it immediately on all its outgoing links - ◆
0 ≤ src < n is the server that sends the broadcast at time 0 - ◆
Return the time at which the LAST server receives the message, or -1 if some server never receives it
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Bellman-Ford Style: Relax Every Link n − 1 Times
BruteKeep the earliest known arrival time of each server (infinity at first, 0 for the sender). Repeat n − 1 times: look at every possible link u → v and, if u has a known time, try to improve v with time[u] + delay. A best route uses at most n − 1 links, so after n − 1 rounds all times are final. Finally return the largest time, or -1 if some server still has infinity. With a matrix each round looks at n² pairs, so O(n³).
O(n³)O(n)1class Solution {
2 public int broadcastTime(int[][] links, int src) {
3 int n = links.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 for (int round = 1; round < n; round++) {
9 for (int u = 0; u < n; u++) {
10 for (int v = 0; v < n; v++) {
11 if (dist[u] != INF && links[u][v] > 0 && dist[u] + links[u][v] < dist[v]) {
12 dist[v] = dist[u] + links[u][v];
13 }
14 }
15 }
16 }
17 int slowest = 0;
18 for (int i = 0; i < n; i++) {
19 if (dist[i] == INF) return -1;
20 slowest = Math.max(slowest, dist[i]);
21 }
22 return slowest;
23 }
24}Optimal — Dijkstra’s Algorithm
OptimalRepeatedly pick the unfinished server with the smallest known arrival time: since all delays are positive, no later route can beat it, so its time is final. Then offer every server it can reach the arrival time plus the link delay, keeping it when smaller. After the rounds, the answer is the largest arrival time (or -1 when some server was never reached). A linear scan for the minimum gives O(n²); adjacency lists with a heap give O((n + E) log n).
O(n²)O(n)1class Solution {
2 public int broadcastTime(int[][] links, int src) {
3 int n = links.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 boolean[] done = new boolean[n];
9 for (int round = 0; round < n; round++) {
10 int u = -1;
11 for (int i = 0; i < n; i++) {
12 if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
13 }
14 if (u == -1 || dist[u] == INF) break;
15 done[u] = true;
16 for (int v = 0; v < n; v++) {
17 if (links[u][v] > 0 && dist[u] + links[u][v] < dist[v]) {
18 dist[v] = dist[u] + links[u][v];
19 }
20 }
21 }
22 int slowest = 0;
23 for (int i = 0; i < n; i++) {
24 if (dist[i] == INF) return -1;
25 slowest = Math.max(slowest, dist[i]);
26 }
27 return slowest;
28 }
29}