The Time When the Network Becomes Idle

Med

#1857Time: 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.2 companies

Algorithms

Breadth-First Search

Data structures

Array Graph

Companies

Atlassian Deutsche Bank

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1import java.util.*;2 3class Solution {4    public int networkBecomesIdle(int[][] edges, int[] patience) {5        int n = patience.length;6        List<List<Integer>> adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10        for (int[] edge : edges) {11            adj.get(edge[0]).add(edge[1]);12            adj.get(edge[1]).add(edge[0]);13        }14 15        int[] dist = new int[n];16        Arrays.fill(dist, -1);17        Queue<Integer> q = new LinkedList<>();18 19        dist[0] = 0;20        q.offer(0);21 22        while (!q.isEmpty()) {23            int u = q.poll();24            for (int v : adj.get(u)) {25                if (dist[v] == -1) {26                    dist[v] = dist[u] + 1;27                    q.offer(v);28                }29            }30        }31 32        int maxTime = 0;33        for (int i = 1; i < n; i++) {34            int rtt = 2 * dist[i];35            int p = patience[i];36            37            int lastMessageArrivalTime;38            if (p >= rtt) {39                lastMessageArrivalTime = rtt;40            } else {41                int numberOfResends = (rtt - 1) / p;42                int lastMessageSendTime = numberOfResends * p;43                lastMessageArrivalTime = lastMessageSendTime + rtt;44            }45            46            if (lastMessageArrivalTime > maxTime) {47                maxTime = lastMessageArrivalTime;48            }49        }50 51        return maxTime + 1;52    }53}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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

1import java.util.*;2 3class Solution {4    public int networkBecomesIdle(int[][] edges, int[] patience) {5        int n = patience.length;6        List<List<Integer>> adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10        for (int[] edge : edges) {11            adj.get(edge[0]).add(edge[1]);12            adj.get(edge[1]).add(edge[0]);13        }14 15        int[] dist = new int[n];16        Arrays.fill(dist, -1);17        Queue<Integer> q = new LinkedList<>();18        dist[0] = 0;19        q.offer(0);20        while (!q.isEmpty()) {21            int u = q.poll();22            for (int v : adj.get(u)) {23                if (dist[v] == -1) {24                    dist[v] = dist[u] + 1;25                    q.offer(v);26                }27            }28        }29 30        PriorityQueue<int[]> eventQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));31        boolean[] receivedFirstReply = new boolean[n];32        33        for (int i = 1; i < n; i++) {34            eventQueue.offer(new int[]{dist[i], 0, i}); // type 0: MSG_TO_MASTER35            eventQueue.offer(new int[]{patience[i], 2, i}); // type 2: RESEND_CHECK36        }37 38        int lastActivityTime = 0;39        while (!eventQueue.isEmpty()) {40            int[] event = eventQueue.poll();41            int time = event[0];42            int type = event[1];43            int serverId = event[2];44 45            if (type == 2 && receivedFirstReply[serverId]) {46                continue;47            }48            49            lastActivityTime = time;50 51            switch (type) {52                case 0: // MSG_TO_MASTER_ARRIVES53                    eventQueue.offer(new int[]{time + dist[serverId], 1, serverId}); // type 1: REPLY_TO_SERVER54                    break;55                case 1: // REPLY_TO_SERVER_ARRIVES56                    if (!receivedFirstReply[serverId]) {57                        receivedFirstReply[serverId] = true;58                    }59                    break;60                case 2: // RESEND_CHECK61                    eventQueue.offer(new int[]{time + dist[serverId], 0, serverId});62                    eventQueue.offer(new int[]{time + patience[serverId], 2, serverId});63                    break;64            }65        }66 67        return lastActivityTime + 1;68    }69}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int networkBecomesIdle(int[][] edges, int[] patience) {4    int n = patience.length;5    List<Integer>[] g = new List[n];6    Arrays.setAll(g, k->new ArrayList<>());7    for (int[] e : edges) {8      int u = e[0], v = e[1];9      g[u].add(v);10      g[v].add(u);11    }12    Deque<Integer> q = new ArrayDeque<>();13    q.offer(0);14    boolean[] vis = new boolean[n];15    vis[0] = true;16    int ans = 0, d = 0;17    while (!q.isEmpty()) {18      ++d;19      int t = d * 2;20      for (int i = q.size(); i > 0; --i) {21        int u = q.poll();22        for (int v : g[u]) {23          if (!vis[v]) {24            vis[v] = true;25            q.offer(v);26            ans = Math.max(ans, (t - 1) / patience[v] * patience[v] + t + 1);27          }28        }29      }30    }31    return ans;32  }33}

1class Solution:2    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

1class Solution {2public:3  int networkBecomesIdle(vector<vector<int>> &edges, vector<int> &patience) {4    int n = patience.size();5    vector<int> g[n];6    for (auto &e : edges) {7      int u = e[0], v = e[1];8      g[u].push_back(v);9      g[v].push_back(u);10    }11    queue<int> q{{0}};12    bool vis[n];13    memset(vis, false, sizeof(vis));14    vis[0] = true;15    int ans = 0, d = 0;16    while (!q.empty()) {17      ++d;18      int t = d * 2;19      for (int i = q.size(); i; --i) {20        int u = q.front();21        q.pop();22        for (int v : g[u]) {23          if (!vis[v]) {24            vis[v] = true;25            q.push(v);26            ans = max(ans, (t - 1) / patience[v] * patience[v] + t + 1);27          }28        }29      }30    }31    return ans;32  }33};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem