LeetCode 2039 - The Time When the Network Becomes Idle

LeetCode Problem 2039

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Graph Theory

Solution

Problem Understanding

This problem involves a network of servers where server 0 is the master and all other servers are data servers. Each data server initially sends a message to the master, and the master instantly responds upon receiving the message. The data servers resend messages periodically if they have not received a reply, according to the patience array. The goal is to determine the earliest second when the network becomes idle, meaning no messages are in transit or pending.

The input consists of an edges list, which describes an undirected graph of servers, and a patience array where patience[i] tells how often server i resends messages. The output is a single integer representing the first second after which the network is idle.

Key points to note are: all servers are connected, patience[0] is 0 (master never resends), messages travel optimally along shortest paths, and each server resends only if the previous message’s reply has not arrived.

Edge cases include servers that are one hop away from the master, servers with patience[i] greater than the round-trip time, and chains or star networks that stress message timing.

Approaches

A brute-force approach would simulate the entire network second by second. Each second, it would move messages along edges, check if replies arrived, and resend messages if needed. While correct, this approach is infeasible for n up to 10^5 because it would require simulating potentially 10^5 seconds for each server, leading to O(n^2) or worse complexity.

The optimal approach relies on two observations. First, messages follow the shortest path, so we can compute the round-trip time (RTT) for each server using a Breadth-First Search (BFS) from the master. Second, a server only resends messages at multiples of its patience[i] before it receives a reply. Using the RTT, we can calculate the last message sent by a server, determine when the reply arrives, and then compute the network idle time efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force Simulation	O(n^2)	O(n + e)	Simulate each second; infeasible for large n
BFS + Math Calculation	O(n + e)	O(n + e)	BFS to get shortest paths; compute last reply times using RTT and patience

Algorithm Walkthrough

Build an adjacency list from edges to represent the network graph. Each node will store a list of its neighbors for efficient traversal.
Initialize a queue for BFS starting at the master server 0. Keep track of visited nodes to avoid revisiting.
Perform BFS to calculate the shortest distance from server 0 to all other servers. Distance here is the number of edges, since each edge takes 1 second.
For each data server i (1 to n-1), compute the round-trip time as 2 * distance[i].
Compute the time of the last message sent by the server before it receives a reply. If round_trip_time <= patience[i], the server sends only one message at time 0. Otherwise, it resends at intervals of patience[i] until just before the reply would arrive.
The network idle time for that server is last_reply_time + 1, where last_reply_time = last_sent_time + round_trip_time.
Return the maximum network idle time among all servers.

Why it works: BFS ensures that we calculate the shortest path from the master server to all servers, which is essential because messages travel optimally. By computing the last reply based on RTT and patience, we can efficiently determine when the network is idle without simulating every second.

Python Solution

from collections import deque
from typing import List

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        dist = [0] * n
        visited = [False] * n
        queue = deque([0])
        visited[0] = True
        
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    dist[neighbor] = dist[node] + 1
                    queue.append(neighbor)
        
        max_idle = 0
        for i in range(1, n):
            rtt = 2 * dist[i]
            if rtt <= patience[i]:
                last_sent = 0
            else:
                last_sent = ((rtt - 1) // patience[i]) * patience[i]
            last_reply = last_sent + rtt
            max_idle = max(max_idle, last_reply + 1)
        
        return max_idle

The Python implementation first builds the adjacency list and runs BFS to find shortest distances from the master. Then, for each data server, it calculates the last message time using integer division to determine the last resend before the reply arrives, computes when that reply returns, and tracks the maximum idle time.

Go Solution

package main

func networkBecomesIdle(edges [][]int, patience []int) int {
    n := len(patience)
    graph := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    dist := make([]int, n)
    visited := make([]bool, n)
    queue := []int{0}
    visited[0] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                dist[neighbor] = dist[node] + 1
                queue = append(queue, neighbor)
            }
        }
    }

    maxIdle := 0
    for i := 1; i < n; i++ {
        rtt := 2 * dist[i]
        var lastSent int
        if rtt <= patience[i] {
            lastSent = 0
        } else {
            lastSent = ((rtt - 1) / patience[i]) * patience[i]
        }
        lastReply := lastSent + rtt
        if lastReply+1 > maxIdle {
            maxIdle = lastReply + 1
        }
    }

    return maxIdle
}

The Go solution mirrors the Python implementation. It uses slices for the adjacency list, a queue for BFS, and integer arithmetic to calculate the last sent message time. Go-specific differences include explicit slice initialization and bounds-aware append operations.

Worked Examples

Example 1: edges = [[0,1],[1,2]], patience = [0,2,1]

BFS distances: [0,1,2], RTT: [0,2,4].

Server 1: RTT=2, patience=2 → last_sent=0, last_reply=2 → idle_time=3
Server 2: RTT=4, patience=1 → last_sent=((4-1)//1)*1=3, last_reply=7 → idle_time=8

Max idle time = 8

Example 2: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]

BFS distances: [0,1,1], RTT: [0,2,2].

Server 1: RTT=2, patience=10 → last_sent=0, last_reply=2 → idle_time=3
Server 2: RTT=2, patience=10 → last_sent=0, last_reply=2 → idle_time=3

Max idle time = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + e)	BFS traverses each node and edge once; calculating idle times is O(n)
Space	O(n + e)	Adjacency list stores edges; distance and visited arrays store n entries

The approach is efficient for large networks because it avoids simulating each second and leverages BFS to compute shortest paths once.

Test Cases

# Provided examples
assert Solution().networkBecomesIdle([[0,1],[1,2]], [0,2,1]) == 8
assert Solution().networkBecomesIdle([[0,1],[0,2],[1,2]], [0,10,10]) == 3

# Simple star network
assert Solution().networkBecomesIdle([[0,1],[0,2],[0,3]], [0,1,2,3]) == 3

# Chain network
assert Solution().networkBecomesIdle([[0,1],[1,2],[2,3]], [0,1,1,1]) == 7

# Minimal input
assert Solution().networkBecomesIdle([[0,1]], [0,1]) == 3

# All patience larger than RTT
assert Solution().networkBecomesIdle([[0,1],[1,2],[2,3]], [0,10,10,10]) == 7

Test	Why
`[[0,1],[1,2]], [