# Dota2 Senate
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/dota2-senate)
Canonical: https://scaleengineer.com/dsa/problems/dota2-senate
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Queue
**Companies:** [Valve](https://scaleengineer.com/companies/valve)
---
## Problem
In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise **one** of the two rights:

* **Ban one senator's right:** A senator can make another senator lose all his rights in this and all the following rounds.
* **Announce the victory:** If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string `senate` representing each senator's party belonging. The character `'R'` and `'D'` represent the Radiant party and the Dire party. Then if there are `n` senators, the size of the given string will be `n`.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be `"Radiant"` or `"Dire"`.

**Example 1:**

**Input:** senate = "RD"
**Output:** "Radiant"
**Explanation:** 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

**Example 2:**

**Input:** senate = "RDD"
**Output:** "Dire"
**Explanation:** 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in round 1. 
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

**Constraints:**

* `n == senate.length`
* `1 <= n <= 104`
* `senate[i]` is either `'R'` or `'D'`.

# Approaches
## Simulation with Boolean Array
This approach directly simulates the round-based voting process described in the problem. We maintain a state for each senator (active or banned) and iterate through the rounds. In each turn, an active senator bans the next available opponent. The simulation continues until only senators of a single party remain.
**Time:** O(n^2). In the worst-case scenario, for each of the `n-1` bans, we might have to scan almost the entire array of `n` senators to find the next opponent. This results in a quadratic time complexity. · **Space:** O(n). We use a boolean array of size `n` to keep track of banned senators.
**Pros:** Intuitive and easy to understand as it directly models the problem description.
**Cons:** Inefficient due to the repeated linear scans for finding opponents to ban.; Likely to result in a "Time Limit Exceeded" error on platforms with larger test cases.
### Explanation
We use a boolean array, `banned`, of the same size as the senate, to keep track of which senators have lost their rights. Initially, all senators are active (`banned[i]` is `false`). We also count the initial number of senators for each party, `radiantCount` and `direCount`. The simulation proceeds in a loop that continues as long as both parties have active senators (`radiantCount > 0 && direCount > 0`). We use an index `i` to iterate through the senators in their given order, wrapping around from the end to the beginning (`i = (i + 1) % n`). If the senator at the current index `i` is active (`!banned[i]`), they get to exercise their right. A Radiant senator will search for the next active Dire senator (starting from `i+1` and wrapping around) and ban them by setting the corresponding `banned` flag to `true` and decrementing `direCount`. Similarly, a Dire senator will ban the next active Radiant senator. If a senator at index `i` is already banned, we simply skip their turn. The process stops when one of the party counts drops to zero. The party with remaining senators is declared the winner. This method is straightforward but inefficient because finding the next opponent to ban requires a linear scan through the senators in the worst case for every single vote.

```java
class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        boolean[] banned = new boolean[n];
        int radiantCount = 0;
        int direCount = 0;
        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') {
                radiantCount++;
            } else {
                direCount++;
            }
        }

        int i = 0;
        while (radiantCount > 0 && direCount > 0) {
            if (!banned[i]) {
                char currentSenator = senate.charAt(i);
                if (currentSenator == 'R') {
                    // Find and ban the next available Dire senator
                    int j = (i + 1) % n;
                    while (true) {
                        if (senate.charAt(j) == 'D' && !banned[j]) {
                            banned[j] = true;
                            direCount--;
                            break;
                        }
                        j = (j + 1) % n;
                    }
                } else { // currentSenator == 'D'
                    // Find and ban the next available Radiant senator
                    int j = (i + 1) % n;
                    while (true) {
                        if (senate.charAt(j) == 'R' && !banned[j]) {
                            banned[j] = true;
                            radiantCount--;
                            break;
                        }
                        j = (j + 1) % n;
                    }
                }
            }
            i = (i + 1) % n;
        }

        return direCount == 0 ? "Radiant" : "Dire";
    }
}
```
### Algorithm
- Initialize a boolean array `banned` of size `n` to all `false`.
- Count the initial number of Radiant (`radiantCount`) and Dire (`direCount`) senators.
- Use a variable `i`, initialized to 0, to track the current senator's turn.
- Loop as long as both `radiantCount > 0` and `direCount > 0`.
- In each iteration, check if `banned[i]` is `false`.
- If it's `false`, the senator at `i` votes. They ban the next available opponent by searching circularly from index `i+1`. Update the `banned` array and the opponent's count.
- Increment `i` and wrap it around using the modulo operator (`i = (i + 1) % n`).
- Once the loop terminates, if `radiantCount > 0`, Radiant wins. Otherwise, Dire wins.

## Greedy Approach with Two Queues
A more efficient approach uses a greedy strategy with two queues. The core idea is that every senator will always try to ban the very next opponent in the voting order to maximize their party's chances. We can model this efficiently using queues to keep track of the indices of active senators for each party.
**Time:** O(n). The initial population of queues takes O(n). Each step of the `while` loop involves constant time queue operations (`poll`, `add`, `isEmpty`) and eliminates one senator. Since there are `n-1` eliminations in total, the loop runs O(n) times. Thus, the total time complexity is linear. · **Space:** O(n). In the worst case, all senators belong to one party, and their indices will be stored in one of the queues.
**Pros:** Highly efficient with linear time complexity.; Elegantly handles the round-based, wrap-around nature of the voting process.
**Cons:** The logic, especially the `+n` trick, might be less intuitive at first glance compared to a direct simulation.
### Explanation
We create two queues: `radiantQueue` to store the indices of Radiant senators and `direQueue` for Dire senators. We populate them by iterating through the input string once. The simulation runs as long as both queues have senators. In each step, we look at the senators at the front of both queues, as they are the next in line to vote for their respective parties. Let the index at the front of `radiantQueue` be `r_idx` and the one at the front of `direQueue` be `d_idx`. The senator with the smaller index gets to vote first. If `r_idx < d_idx`, the Radiant senator at `r_idx` bans the Dire senator at `d_idx`. The Dire senator is removed from their queue (`direQueue.poll()`). The Radiant senator has used their turn for this round and will get to vote in the next round. To signify this, we add their index back to their queue, but with `n` added to it (`radiantQueue.add(r_idx + n)`). This clever trick ensures they are placed at the end of the queue for the next round while maintaining the relative order of senators. If `d_idx < r_idx`, the Dire senator bans the Radiant senator, and we perform the symmetric operation. The process continues until one queue becomes empty. The party corresponding to the non-empty queue is the winner.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        Queue<Integer> radiantQueue = new LinkedList<>();
        Queue<Integer> direQueue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') {
                radiantQueue.add(i);
            } else {
                direQueue.add(i);
            }
        }

        while (!radiantQueue.isEmpty() && !direQueue.isEmpty()) {
            int rIndex = radiantQueue.poll();
            int dIndex = direQueue.poll();

            if (rIndex < dIndex) {
                // Radiant senator at rIndex is first, bans the Dire senator.
                // The Radiant senator's right is carried to the next round.
                radiantQueue.add(rIndex + n);
            } else {
                // Dire senator at dIndex is first, bans the Radiant senator.
                // The Dire senator's right is carried to the next round.
                direQueue.add(dIndex + n);
            }
        }

        return radiantQueue.isEmpty() ? "Dire" : "Radiant";
    }
}
```
### Algorithm
- Create two queues, `radiantQueue` and `direQueue`.
- Iterate through the `senate` string from `i = 0` to `n-1`. If `senate[i]` is 'R', add `i` to `radiantQueue`. Otherwise, add `i` to `direQueue`.
- Loop while both `radiantQueue` and `direQueue` are not empty.
- Dequeue the top elements: `r_idx = radiantQueue.poll()` and `d_idx = direQueue.poll()`.
- Compare their original indices. If `r_idx < d_idx`, the Radiant senator votes. Enqueue `r_idx + n` into `radiantQueue`.
- Otherwise, the Dire senator votes. Enqueue `d_idx + n` into `direQueue`.
- After the loop, if `radiantQueue` is empty, return "Dire". Otherwise, return "Radiant".

# Solutions
### Java

```java
class Solution { public String predictPartyVictory ( String senate ) { int n = senate . length (); Deque < Integer > qr = new ArrayDeque <>(); Deque < Integer > qd = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { if ( senate . charAt ( i ) == 'R' ) { qr . offer ( i ); } else { qd . offer ( i ); } } while (! qr . isEmpty () && ! qd . isEmpty ()) { if ( qr . peek () < qd . peek ()) { qr . offer ( qr . peek () + n ); } else { qd . offer ( qd . peek () + n ); } qr . poll (); qd . poll (); } return qr . isEmpty () ? "Dire" : "Radiant" ; } }
```

### CPP

```cpp
class Solution { public: string predictPartyVictory ( string senate ) { int n = senate . size (); queue < int > qr ; queue < int > qd ; for ( int i = 0 ; i < n ; ++ i ) { if ( senate [ i ] == 'R' ) { qr . push ( i ); } else { qd . push ( i ); } } while ( ! qr . empty () && ! qd . empty ()) { int r = qr . front (); int d = qd . front (); qr . pop (); qd . pop (); if ( r < d ) { qr . push ( r + n ); } else { qd . push ( d + n ); } } return qr . empty () ? "Dire" : "Radiant" ; } };
```

### Python

```python
class Solution : def predictPartyVictory ( self , senate : str ) -> str : qr = deque () qd = deque () for i , c in enumerate ( senate ): if c == "R" : qr . append ( i ) else : qd . append ( i ) n = len ( senate ) while qr and qd : if qr [ 0 ] < qd [ 0 ]: qr . append ( qr [ 0 ] + n ) else : qd . append ( qd [ 0 ] + n ) qr . popleft () qd . popleft () return "Radiant" if qr else "Dire"
```