Sponsored
Sponsored
We utilize two separate queues to maintain indices of Radiant and Dire senators. In each round, senators from both parties execute their rights and effect bans on their opponent. The process continues until one queue becomes empty, indicating that all senators from one party have been eliminated.
Time Complexity: O(n), where n is the length of the senate, since each senator is processed a finite number of times.
Space Complexity: O(n), for storing indices in queues.
1from collections import deque
2
3def predict_party_victory(senate: str) -> str:
4 radiant = deque()
5 dire = deque()
6
7 for i, s in enumerate(senate):
8 if s == 'R':
9 radiant.append(i)
10 else:
11 dire.append(i)
12
13 length = len(senate)
14 while radiant and dire:
15 r_idx = radiant.popleft()
16 d_idx = dire.popleft()
17 if r_idx < d_idx:
18 radiant.append(r_idx + length)
19 else:
20 dire.append(d_idx + length)
21
22 return "Radiant" if radiant else "Dire"
23Here, we utilize Python’s deque structure from the collections module to maintain efficient access and insertion of senatorial indices. The indices are compared round by round, and the simulation proceeds until a party is banned completely.