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.
1#include <iostream>
2#include <queue>
3using namespace std;
4
5string predictPartyVictory(string senate) {
6 int n = senate.size();
7 queue<int> radiant, dire;
8 for (int i = 0; i < n; ++i) {
9 if (senate[i] == 'R') radiant.push(i);
10 else dire.push(i);
11 }
12 while (!radiant.empty() && !dire.empty()) {
13 int rIdx = radiant.front(); radiant.pop();
14 int dIdx = dire.front(); dire.pop();
15 if (rIdx < dIdx) radiant.push(rIdx + n);
16 else dire.push(dIdx + n);
17 }
18 return radiant.empty() ? "Dire" : "Radiant";
19}
20This C++ solution uses standard library queues to store the current indices of Radiant and Dire senators. Depending on which senator appears earlier, it bans the senator from the opposition and its index is extended for the next voting round. The process loops until one queue is empty.