# The Time When the Network Becomes Idle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-time-when-the-network-becomes-idle)
Canonical: https://scaleengineer.com/dsa/problems/the-time-when-the-network-becomes-idle
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Graph
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank)
---
## 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**_.

**Example 1:**

![example 1](https://assets.glich.co/dsa/the-time-when-the-network-becomes-idle/image0.png) 

**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:**

![example 2](https://assets.glich.co/dsa/the-time-when-the-network-becomes-idle/image1.png) 

**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 <= 105`
* `patience[0] == 0`
* `1 <= patience[i] <= 105` for `1 <= i < n`
* `1 <= edges.length <= min(105, 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 another server.

# Approaches
## Event-Driven Simulation
This approach simulates the entire process of message passing and resending over time. It uses an event-driven model, where events like 'message arrives at master' or 'server checks to resend' are processed in chronological order using a priority queue. The simulation continues until all message activity ceases, and the time of the last event determines when the network becomes idle.
**Time:** O(n + E + S * log(S)), where `n` is the number of servers, `E` is the number of edges, and `S` is the total number of events. In the worst case, `S` can be on the order of `O(n^2)`, making the simulation too slow. · **Space:** O(n + E + S), where `S` is the total number of simulation events. The adjacency list takes `O(n + E)` space. The priority queue can hold up to `S` events, which can be `O(n^2)` in the worst case, making the space complexity prohibitive.
**Pros:** Conceptually straightforward, as it directly models the problem description.; Can be adapted to more complex scenarios where an analytical solution is not obvious.
**Cons:** The time complexity is prohibitive for the given constraints (`n` up to 10^5), as the number of events can be quadratic in the number of servers.; The space complexity can also be very high due to the large number of events stored in the priority queue.; It is more complex to implement correctly compared to a direct analytical solution.
### Explanation
1.  **Prerequisites**: Similar to the efficient approach, we first need to build the graph's adjacency list and run a BFS from the master server (0) to find the shortest travel time `dist[i]` for each server `i`.
2.  **Event Queue**: A priority queue is used to manage events. Each event is a tuple `(time, type, serverId)`, ordered by `time`. The possible event types are:
    *   `MSG_TO_MASTER_ARRIVES`: A message from a data server arrives at the master.
    *   `REPLY_TO_SERVER_ARRIVES`: A reply from the master arrives at a data server.
    *   `RESEND_CHECK`: A data server checks if it needs to resend its message.
3.  **Initialization**:
    *   Create a boolean array `receivedReply` of size `n`, initialized to `false`, to track which servers have received their first reply.
    *   For each data server `i` (from 1 to `n-1`):
        *   The initial message is sent at `t=0`. Schedule its arrival at the master: add `(dist[i], MSG_TO_MASTER_ARRIVES, i)` to the priority queue.
        *   Schedule the first resend check: add `(patience[i], RESEND_CHECK, i)` to the priority queue.
4.  **Simulation Loop**:
    *   Maintain a variable `lastActivityTime`, initialized to 0.
    *   While the priority queue is not empty, extract the event with the earliest time.
    *   Update `lastActivityTime` to the time of the current event.
    *   Process the event based on its type:
        *   If `MSG_TO_MASTER_ARRIVES` for server `i` at time `t`: The master instantly sends a reply. Schedule the reply's arrival: add `(t + dist[i], REPLY_TO_SERVER_ARRIVES, i)` to the queue.
        *   If `REPLY_TO_SERVER_ARRIVES` for server `i`: Mark `receivedReply[i] = true`. This server will no longer schedule resends.
        *   If `RESEND_CHECK` for server `i` at time `t`: If `receivedReply[i]` is `false`, the server resends its message. Schedule its arrival at the master: add `(t + dist[i], MSG_TO_MASTER_ARRIVES, i)`. Also, schedule the *next* resend check for this server: add `(t + patience[i], RESEND_CHECK, i)` to the queue.
5.  **Final Answer**: After the loop finishes (the queue is empty), `lastActivityTime` holds the time of the last message arrival. The network becomes idle at the next second, so the answer is `lastActivityTime + 1`.

```java
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);
                }
            }
        }

        PriorityQueue<int[]> eventQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        boolean[] receivedFirstReply = new boolean[n];
        
        for (int i = 1; i < n; i++) {
            eventQueue.offer(new int[]{dist[i], 0, i}); // type 0: MSG_TO_MASTER
            eventQueue.offer(new int[]{patience[i], 2, i}); // type 2: RESEND_CHECK
        }

        int lastActivityTime = 0;
        while (!eventQueue.isEmpty()) {
            int[] event = eventQueue.poll();
            int time = event[0];
            int type = event[1];
            int serverId = event[2];

            if (type == 2 && receivedFirstReply[serverId]) {
                continue;
            }
            
            lastActivityTime = time;

            switch (type) {
                case 0: // MSG_TO_MASTER_ARRIVES
                    eventQueue.offer(new int[]{time + dist[serverId], 1, serverId}); // type 1: REPLY_TO_SERVER
                    break;
                case 1: // REPLY_TO_SERVER_ARRIVES
                    if (!receivedFirstReply[serverId]) {
                        receivedFirstReply[serverId] = true;
                    }
                    break;
                case 2: // RESEND_CHECK
                    eventQueue.offer(new int[]{time + dist[serverId], 0, serverId});
                    eventQueue.offer(new int[]{time + patience[serverId], 2, serverId});
                    break;
            }
        }

        return lastActivityTime + 1;
    }
}
```
### Algorithm
- **Graph Representation**: Model the server network as a graph using an adjacency list.
- **Shortest Path Pre-computation**: Run a Breadth-First Search (BFS) starting from the master server (node 0) to calculate the shortest travel time `dist[i]` for a message from any server `i` to the master.
- **Event-Driven Simulation**: Use a priority queue to manage and process events in chronological order. Events can be of three types: a message arriving at the master, a reply arriving at a data server, or a data server checking if it needs to resend a message.
- **Initialization**: 
  - For each data server `i`, schedule two initial events: the arrival of its first message at the master at time `dist[i]`, and its first resend check at time `patience[i]`.
  - Use a boolean array `receivedFirstReply` to track if a server has received its first reply and should stop resending.
- **Simulation Loop**: 
  - Repeatedly extract the event with the smallest timestamp from the priority queue.
  - Keep track of the time of the last processed event in a variable `lastActivityTime`.
  - Process the event:
    - **Message Arrival at Master**: Schedule a corresponding reply arrival event for that server.
    - **Reply Arrival at Server**: Mark the server as having received its reply.
    - **Resend Check**: If the server has not yet received a reply, resend the message (schedule a new message arrival at the master) and schedule the next resend check.
- **Termination**: The simulation ends when the event queue is empty. The final answer is `lastActivityTime + 1`.

## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.

1.  **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`.

2.  **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.

3.  **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`.

4.  **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`.

```java
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;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int: g = defaultdict(list) for u, v in edges: g[u]. append(v) g[v]. append(u) q = deque([0]) vis = {0} ans = d = 0 while q: d += 1 t = d * 2 for _ in range(len(q)): u = q . popleft() for v in g[u]: if v not in vis: vis . add(v) q . append(v) ans = max(ans, (t - 1) // patience[v] * patience[v] + t + 1) return ans

```

### CPP

```cpp
class Solution {
public:
  int networkBecomesIdle(vector<vector<int>> &edges, vector<int> &patience) {
    int n = patience.size();
    vector<int> g[n];
    for (auto &e : edges) {
      int u = e[0], v = e[1];
      g[u].push_back(v);
      g[v].push_back(u);
    }
    queue<int> q{{0}};
    bool vis[n];
    memset(vis, false, sizeof(vis));
    vis[0] = true;
    int ans = 0, d = 0;
    while (!q.empty()) {
      ++d;
      int t = d * 2;
      for (int i = q.size(); i; --i) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
          if (!vis[v]) {
            vis[v] = true;
            q.push(v);
            ans = max(ans, (t - 1) / patience[v] * patience[v] + t + 1);
          }
        }
      }
    }
    return ans;
  }
};

```