The Time When the Network Becomes Idle — Medium Problem & Solution

Problem statement

A network has n servers labelled 0 to n - 1, joined by the two-way links in edges (each [ui, vi]); every server can reach every other. Server 0 is the master; the rest are data servers. A message crosses one link per second, and every message always takes a shortest route.

At second 0, each data server sends a message to the master. The master processes messages instantly and sends each reply straight back along a shortest route.

Data server i checks at the start of every second: if its reply has not arrived and patience[i] seconds have passed since it last sent, it resends the message. Once its reply arrives, it stops sending. The master never sends anything on its own.

The network is idle at the first second when no message or reply is travelling or arriving. Return that second.

Example 1

Input: edges = [[0,1],[1,2],[1,3]], patience = [0,3,2,5]
Output: 7
Explanation: Server 2 is two links away, so its reply takes 4 seconds; it resends at second 2, whose reply lands at second 6. Nothing travels at second 7.

Example 2

Input: edges = [[0,1],[0,2]], patience = [0,1,4]
Output: 4

Constraints

• n == patience.length
• 2 <= n <= 10^5
• patience[0] == 0
• 1 <= patience[i] <= 10^5 for i >= 1
• 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• no duplicate edges; every server can reach every other

How to solve The Time When the Network Becomes Idle

Each server behaves independently: once you know its distance to the master, you can compute exactly when its final reply arrives.

Approach

1. BFS from server 0 to get every server's distance d.
2. For server i, the round trip is t = 2d. It resends at multiples of patience[i] that fall strictly before t, so its last send is at ((t − 1) / patience[i]) · patience[i].
3. That message's reply arrives at last + t; the network goes quiet one second after the latest such arrival.
4. Return max(last + t over all i) + 1.

Why it works

Messages are routed along shortest paths and never interfere, so every message from server i takes exactly t seconds to come back. The server stops resending at second t, when the first reply arrives; any multiple of patience[i] below t triggers a resend. The latest event in the whole network is therefore the latest reply among all servers, and the next second is the first idle one.

Complexity

• Time — O(n + m)
• Space — O(n + m)

Pitfalls

• A resend at exactly second t does not happen — the reply arrives at that moment; hence t − 1 in the formula.
• Answer the first idle second, which is one more than the last arrival.
• The master's patience[0] is 0 — skip server 0 to avoid dividing by zero.

Reference solution

Python

from typing import List
from collections import deque

def networkBecomesIdle(edges: List[List[int]], patience: List[int]) -> int:
    n = len(patience)
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    dist = [-1] * n
    dist[0] = 0
    q = deque([0])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] < 0:
                dist[v] = dist[u] + 1
                q.append(v)
    ans = 0
    for i in range(1, n):
        t = 2 * dist[i]
        last = (t - 1) // patience[i] * patience[i]
        ans = max(ans, last + t)
    return ans + 1

JavaScript

var networkBecomesIdle = function(edges, patience) {
    var n = patience.length;
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    var dist = [];
    for (var k = 0; k < n; k++) dist.push(-1);
    dist[0] = 0;
    var queue = [0];
    for (var h = 0; h < queue.length; h++) {
        var u = queue[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (dist[v] < 0) { dist[v] = dist[u] + 1; queue.push(v); }
        }
    }
    var ans = 0;
    for (var s = 1; s < n; s++) {
        var t = 2 * dist[s];
        var last = Math.floor((t - 1) / patience[s]) * patience[s];
        if (last + t > ans) ans = last + t;
    }
    return ans + 1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium