The Time When the Network Becomes Idle

MEDIUM

Description

There is a network of n servers, labeled from 0 to n - 1. You are given a 2D integer array edges, where edges[i] = [u_i, v_i] indicates there is a message channel between servers u_i and v_i, 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.

Example 1:

Input: edges = [[0,1],[1,2]], patience = [0,2,1]
Output: 8
Explanation:
At (the beginning of) second 0,
- Data server 1 sends its message (denoted 1A) to the master server.
- Data server 2 sends its message (denoted 2A) to the master server.

At second 1,
- Message 1A arrives at the master server. Master server processes message 1A instantly and sends a reply 1A back.
- Server 1 has not received any reply. 1 second (1 < patience[1] = 2) elapsed since this server has sent the message, therefore it does not resend the message.
- Server 2 has not received any reply. 1 second (1 == patience[2] = 1) elapsed since this server has sent the message, therefore it resends the message (denoted 2B).

At second 2,
- The reply 1A arrives at server 1. No more resending will occur from server 1.
- Message 2A arrives at the master server. Master server processes message 2A instantly and sends a reply 2A back.
- Server 2 resends the message (denoted 2C).
...
At second 4,
- The reply 2A arrives at server 2. No more resending will occur from server 2.
...
At second 7, reply 2D arrives at server 2.

Starting from the beginning of the second 8, there are no messages passing between servers or arriving at servers.
This is the time when the network becomes idle.

Example 2:

Input: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
Output: 3
Explanation: Data servers 1 and 2 receive a reply back at the beginning of second 2.
From the beginning of the second 3, the network becomes idle.

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 <= u_i, v_i < n
u_i != v_i
There are no duplicate edges.
Each server can directly or indirectly reach another server.

Approaches

Checkout 2 different approaches to solve The Time When the Network Becomes Idle. Click on different approaches to view the approach and algorithm in detail.

BFS to Find Distances and Analytical Calculation

This approach avoids a full simulation by first using Breadth-First Search (BFS) to find the shortest time for a message to travel from each data server to the master server. Then, for each data server, it analytically calculates when the last message activity (sending or receiving) related to that server will conclude. The overall network idle time is determined by the maximum of these individual server idle times.

Algorithm

Graph Representation: Model the server network as a graph. Build an adjacency list from the edges input, where adj[u] contains all servers v connected to u.
Shortest Path Calculation: Since each message channel takes one second, the problem is equivalent to finding the shortest path in an unweighted graph. Use Breadth-First Search (BFS) starting from the master server (node 0) to compute the shortest distance dist[i] to every other server i.
Per-Server Idle Time Calculation: Iterate through each data server i from 1 to n-1:
- Calculate the round-trip time (RTT) for its first message: rtt = 2 * dist[i].
- Get the server's patience: p = patience[i].
- If p >= rtt, no resends occur. The last activity is the arrival of the first reply at time rtt.
- If p < rtt, the server resends. Calculate the time of the last resent message: last_send_time = ((rtt - 1) / p) * p. The reply to this last message arrives at last_arrival_time = last_send_time + rtt. This is the last activity time for this server.
Overall Idle Time: The entire network becomes idle after the last message for any server has arrived. Find the maximum of all calculated last arrival times. Let this be max_last_activity.
Final Answer: The network is idle starting from the second after the last activity. The result is max_last_activity + 1.

The core idea is to determine, for each data server, the arrival time of the very last message associated with it. The network becomes idle one second after the last of these messages arrives anywhere in the network.

Find Shortest Paths with BFS: The time it takes for a message to travel between two servers is the number of hops on the shortest path. We can find the shortest path distance from the master server (0) to all other data servers using a single Breadth-First Search (BFS) traversal starting from node 0. Let dist[i] be the shortest distance from server 0 to server i.
Analyze each Data Server: For each data server i (from 1 to n-1):
- A message sent from server i reaches the master in dist[i] seconds. The master's reply takes another dist[i] seconds to travel back. So, the total round-trip time (RTT) is 2 * dist[i].
- Server i receives the reply to its first message at time t = 2 * dist[i]. After this time, it stops sending new messages.
- While waiting for this reply, server i resends messages every patience[i] seconds. The last message it sends will be at time t_last_send, which must be less than the arrival time of the first reply, 2 * dist[i].
- We can calculate t_last_send. If patience[i] is greater than or equal to the RTT, no resends happen. The only message's reply arrives at RTT. Otherwise, the number of resends is k = (RTT - 1) / patience[i]. The last message is sent at t_last_send = k * patience[i].
- The reply for this last message will arrive RTT seconds after it was sent, i.e., at t_last_arrival = t_last_send + RTT.
- This t_last_arrival is the time the communication channel for server i becomes quiet.
Determine Global Idle Time: The entire network is idle only when all servers are quiet. Therefore, we need to find the maximum t_last_arrival among all data servers. Let this be max_time.
Final Result: The network becomes idle at the beginning of the second immediately following the last message arrival. Thus, the answer is max_time + 1.

import java.util.*;

class Solution {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();

        dist[0] = 0;
        q.offer(0);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i < n; i++) {
            int rtt = 2 * dist[i];
            int p = patience[i];
            
            int lastMessageArrivalTime;
            if (p >= rtt) {
                lastMessageArrivalTime = rtt;
            } else {
                int numberOfResends = (rtt - 1) / p;
                int lastMessageSendTime = numberOfResends * p;
                lastMessageArrivalTime = lastMessageSendTime + rtt;
            }
            
            if (lastMessageArrivalTime > maxTime) {
                maxTime = lastMessageArrivalTime;
            }
        }

        return maxTime + 1;
    }
}

Complexity Analysis

Time Complexity: O(n + E), where `n` is the number of servers and `E` is the number of edges. Building the adjacency list takes `O(E)`. The BFS takes `O(n + E)`. The final loop to calculate the max idle time takes `O(n)`. The total time complexity is dominated by BFS.Space Complexity: O(n + E), where `n` is the number of servers and `E` is the number of edges. The adjacency list requires `O(n + E)` space. The `dist` array and the BFS queue require `O(n)` space.

Pros and Cons

Pros:

Highly efficient, with a time complexity linear in the size of the graph.
Avoids a complex and slow simulation by calculating the result directly.
Optimal in terms of both time and space complexity.

Cons:

Requires a clear understanding of the problem's timing mechanics to derive the correct analytical formula for the last message arrival.

Code Solutions

Checking out 3 solutions in different languages for The Time When the Network Becomes Idle. Click on different languages to view the code.

class Solution {
public
  int networkBecomesIdle(int[][] edges, int[] patience) {
    int n = patience.length;
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int[] e : edges) {
      int u = e[0], v = e[1];
      g[u].add(v);
      g[v].add(u);
    }
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(0);
    boolean[] vis = new boolean[n];
    vis[0] = true;
    int ans = 0, d = 0;
    while (!q.isEmpty()) {
      ++d;
      int t = d * 2;
      for (int i = q.size(); i > 0; --i) {
        int u = q.poll();
        for (int v : g[u]) {
          if (!vis[v]) {
            vis[v] = true;
            q.offer(v);
            ans = Math.max(ans, (t - 1) / patience[v] * patience[v] + t + 1);
          }
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for The Time When the Network Becomes Idle

Algorithms:

Breadth-First Search

Data Structures:

ArrayGraph

Companies:

Atlassian |Deutsche Bank |