#2039
The Time When the Network Becomes Idle
MediumArrayBreadth-First SearchGraph TheoryGraph TraversalBFS
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
The optimal solution uses BFS to efficiently find the shortest distance from the master server to each data server. We then calculate when the last message will be sent back based on the server's patience, ensuring we minimize unnecessary calculations.
⚙️
Algorithm
4 steps- 1Step 1: Build the graph from the edges.
- 2Step 2: Use BFS to find the shortest distance from the master server (server 0) to all other servers.
- 3Step 3: For each data server, calculate the time it will take for the last message to be sent back considering its patience value.
- 4Step 4: Return the maximum time among all data servers when the last message is sent back.
solution.py27 lines
1from collections import deque
2
3def networkIdleTime(edges, patience):
4 n = len(patience)
5 graph = [[] for _ in range(n)]
6 for u, v in edges:
7 graph[u].append(v)
8 graph[v].append(u)
9
10 dist = [float('inf')] * n
11 dist[0] = 0
12 queue = deque([0])
13
14 while queue:
15 node = queue.popleft()
16 for neighbor in graph[node]:
17 if dist[neighbor] == float('inf'):
18 dist[neighbor] = dist[node] + 1
19 queue.append(neighbor)
20
21 max_time = 0
22 for i in range(1, n):
23 time_to_master = dist[i]
24 last_message_time = (time_to_master * 2) + ((time_to_master * 2) // patience[i]) * patience[i]
25 max_time = max(max_time, last_message_time)
26
27 return max_time + 1ℹ
Complexity note: The time complexity is O(n) because we only traverse each node once using BFS, which is efficient for this problem.
- 1Understanding BFS for shortest path in graphs is crucial.
- 2Patience values dictate when servers resend messages.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.