649. Dota2 Senate

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

1. Initialization: - Create two queues to store the indices of senators from each party. radiant for "R" senators and dire for "D" senators.
2. Populate Queues: - Traverse the input string and enqueue the indices of each senator based on their party affiliation.
3. 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.
4. 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