
Description
The problem involves determining the winner of a Senate voting game between two parties: "Radiant" (R) and "Dire" (D). Each senator in the Senate has a chance to eliminate an opponent senator in each round. The goal is to find out which party will win, given that senators with fewer votes will be eliminated, and the remaining senators will continue the process.
Intuition
To solve this problem, we need to simulate the elimination process by keeping track of the positions of the senators from each party. By using two queues, we can effectively manage the turn-based elimination process and determine the winner.
Approach
- Initialization:
- Create two queues to store the indices of senators from each party.
radiant
for "R" senators anddire
for "D" senators. - Populate Queues: - Traverse the input string and enqueue the indices of each senator based on their party affiliation.
- Simulation: - While both queues are not empty, dequeue the first senator from each party. Compare their indices: - The senator with the smaller index eliminates the one with the larger index. - The eliminated senator's index is updated to simulate future rounds and is added back to the end of their respective queue.
- Determine the Winner:
- The process continues until one of the queues is empty.
- If the
radiant
queue is empty, "Dire" wins. Otherwise, "Radiant" wins.
Complexity
Time Complexity:
O(n), where n is the length of the senate
string. Each senator is processed a constant number of times (adding and removing from the queue).
Space Complexity:
O(n), where n is the length of the senate
string. We store all the indices in the queues.
Code
C++
class Solution {
public:
string predictPartyVictory(string senate) {
deque dq(senate.begin(), senate.end());
while (!dq.empty()) {
char first = dq.front();
dq.pop_front();
int len = dq.size();
bool foundOpponent = false;
for (int i = 0; i < len; ++i) {
if (first != dq[i]) {
dq.erase(dq.begin() + i);
dq.push_back(first);
foundOpponent = true;
break;
}
}
if (!foundOpponent) {
return (first == 'D') ? "Dire" : "Radiant";
}
}
return ""; // Should never reach here
}
};
Python
class Solution:
def predictPartyVictory(self, senate: str) -> str:
radiant = deque()
dire = deque()
# Populate the queues with indices of senators
for i, char in enumerate(senate):
if char == 'R':
radiant.append(i)
else:
dire.append(i)
# Simulate the process
while radiant and dire:
r_index = radiant.popleft()
d_index = dire.popleft()
# The senator with the smaller index will be eliminated
if r_index < d_index:
radiant.append(r_index + len(senate))
else:
dire.append(d_index + len(senate))
# Determine the winner
return "Dire" if not radiant else "Radiant"
Java
public class Solution {
public String predictPartyVictory(String senate) {
Queue radiant = new LinkedList<>();
Queue dire = new LinkedList<>();
// Populate the queues with indices of senators
for (int i = 0; i < senate.length(); i++) {
if (senate.charAt(i) == 'R') {
radiant.add(i);
} else {
dire.add(i);
}
}
// Simulate the process
while (!radiant.isEmpty() && !dire.isEmpty()) {
int rIndex = radiant.poll();
int dIndex = dire.poll();
// The senator with the smaller index will be eliminated
if (rIndex < dIndex) {
radiant.add(rIndex + senate.length());
} else {
dire.add(dIndex + senate.length());
}
}
// Determine the winner
return radiant.isEmpty() ? "Dire" : "Radiant";
}
}
JavaScript
var predictPartyVictory = function(senate) {
senate = senate.split('');
while(senate.length) {
var first = senate.shift();
var len = senate.length;
for(var i=0; i