The Time When the Network Becomes Idle - Practice Coding Problems

The Time When the Network Becomes Idle - Problem

There is a network of n servers, labeled from 0 to n - 1. You are given a 2D integer array edges, where edges[i] = [ui, vi] indicates there is a message channel between servers ui and vi, and they can pass any number of messages to each other directly in one second.

You are also given a 0-indexed integer array patience of length n.

All servers are connected, i.e., a message can be passed from one server to any other server(s) directly or indirectly through the message channels.

The server labeled 0 is the master server. The rest are data servers. Each data server needs to send its message to the master server for processing and wait for a reply. Messages move between servers optimally, so every message takes the least amount of time to arrive at the master server. The master server will process all newly arrived messages instantly and send a reply to the originating server via the reversed path the message had gone through.

At the beginning of second 0, each data server sends its message to be processed. Starting from second 1, at the beginning of every second, each data server will check if it has received a reply to the message it sent (including any newly arrived replies) from the master server:

If it has not, it will resend the message periodically. The data server i will resend the message every patience[i] second(s), i.e., the data server i will resend the message if patience[i] second(s) have elapsed since the last time the message was sent from this server.
Otherwise, no more resending will occur from this server.

The network becomes idle when there are no messages passing between servers or arriving at servers.

Return the earliest second starting from which the network becomes idle.

Input & Output

Example 1 — Basic Network

$ Input: edges = [[0,1],[1,2]], patience = [0,2,1]

› Output: 8

💡 Note: Server 1 (distance 1): round trip = 2, patience = 2, no resending needed, idle at time 2+1 = 3. Server 2 (distance 2): round trip = 4, patience = 1, resends at times 0,1,2,3, last send at 3, idle at time 3+4 = 7+1 = 8.

Example 2 — No Resending

$ Input: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]

› Output: 3

💡 Note: Both servers 1 and 2 have distance 1, round trip = 2. Since patience ≥ round trip, no resending occurs. Network idle at time 2+1 = 3.

Example 3 — Multiple Resends

$ Input: edges = [[0,1],[1,2],[2,3]], patience = [0,1,1,1]

› Output: 8

💡 Note: Server 3 has distance 3, round trip = 6, patience = 1. Resends every second until reply arrives. Last send at time 5, idle at time 5+6 = 11, but other servers finish earlier, so answer is calculated from the maximum.

Constraints

n == patience.length
2 ≤ n ≤ 10⁵
patience[0] == 0
1 ≤ patience[i] ≤ 10⁵ for 1 ≤ i < n
1 ≤ edges.length ≤ min(10⁵, n × (n - 1) / 2)
edges[i].length == 2
0 ≤ ui, vi < n
ui != vi
There are no duplicate edges
Each server can directly or indirectly reach every other server

Visualization

Tap to expand

Understanding the Visualization

Network Setup

Master server (0) connected to data servers via edges

Message Flow

Each data server sends messages and waits for replies

Idle Calculation

Network becomes idle when all messages complete round trips

Key Takeaway

🎯 Key Insight: Calculate mathematically when each server's last message completes its round trip, rather than simulating every second

Asked in

G Google 15 M Microsoft 12

Use BFS from master server to find shortest distances to all servers. For each server, calculate when its last message completes the round trip. The network becomes idle one second after the maximum idle time. Key insight: last_send_time = ((round_trip - 1) / patience) * patience. Time: O(V + E), Space: O(V + E).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(T × n)	O(n²)	Simulate every second and track all messages in the network
BFS + Mathematical Calculation	O(V + E)	O(V + E)	Use BFS to find shortest paths, then calculate idle time mathematically

Simulation Approach — Algorithm Steps

Build graph from edges
Simulate second by second
Track messages and replies
Check when network becomes idle

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Build graph and initialize message tracking

Simulate

For each second, process sends/receives/resends

Check Idle

Continue until no messages are in transit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int edges[][2], int edgesSize, int* patience, int patienceSize) {
    int n = patienceSize;
    
    // Build adjacency list (simplified for basic case)
    int graph[1000][1000]; // Assuming max 1000 nodes
    int graphSize[1000] = {0};
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    // Find shortest distances using BFS
    int distances[1000];
    for (int i = 0; i < n; i++) {
        distances[i] = -1;
    }
    distances[0] = 0;
    
    int queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = 0;
    
    while (front < rear) {
        int node = queue[front++];
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (distances[neighbor] == -1) {
                distances[neighbor] = distances[node] + 1;
                queue[rear++] = neighbor;
            }
        }
    }
    
    int maxIdleTime = 0;
    
    // For each data server (1 to n-1)
    for (int i = 1; i < n; i++) {
        // Round trip time to master and back
        int roundTrip = 2 * distances[i];
        
        // Find when last message is sent before first reply arrives
        int lastSendTime;
        if (patience[i] >= roundTrip) {
            // No resending needed
            lastSendTime = 0;
        } else {
            // Calculate last resend time before first reply
            lastSendTime = ((roundTrip - 1) / patience[i]) * patience[i];
        }
        
        // Time when this server becomes idle
        int idleTime = lastSendTime + roundTrip;
        if (idleTime > maxIdleTime) {
            maxIdleTime = idleTime;
        }
    }
    
    return maxIdleTime + 1;
}

int main() {
    // Simplified input parsing
    int edges[1000][2];
    int edgesSize = 0;
    int patience[1000];
    int patienceSize = 0;
    
    // Read edges (basic parsing)
    char line[10000];
    fgets(line, sizeof(line), stdin);
    // Parse edges from string
    
    // Read patience (basic parsing)
    fgets(line, sizeof(line), stdin);
    // Parse patience from string
    
    int result = solution(edges, edgesSize, patience, patienceSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(T × n)

T can be very large (thousands of seconds), simulating each second for n servers

✓ Linear Growth

Space Complexity

O(n²)

Need to store graph and track messages for each server

⚠ Quadratic Space

18.0K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler