dota2 Senate

Problem Link

Problem Statement

In the Dota2 world, there are two parties: Radiant ('R') and Dire ('D'). The senate consists of n senators from these two parties, and the game is played in rounds.

Each round, in order:

Each unbanned senator can ban one senator from the opposing party.
Once a senator is banned, they cannot act in future rounds.
The round continues until only one party remains.

Return the winning party as a string:

"Radiant" if Radiant wins.
"Dire" if Dire wins.

Examples

Example 1:

Input: senate = "RD"
Output: "Radiant"
Explanation:
R acts first and bans D → only R remains

Example 2:

Input: senate = "RDD"
Output: "Dire"
Explanation:
R bans D → D remains → D bans R → only D remains

Constraints

n == senate.length
1 <= n <= 10⁴
senate[i] is either 'R' or 'D'

Intuition

This problem is essentially a turn-based simulation. The key observation is:

A senator at index i can only ban someone after them in the current round or in the next round by cycling back.
So we track the indices of 'R' and 'D' senators separately in two queues.
In each round, the senator with the smaller index gets to ban the other and returns to the queue with index +n to simulate next round participation.

Approach: Queue-Based Round Simulation

Initialize two queues:
- rQ: Indices of Radiant senators.
- dQ: Indices of Dire senators.
Traverse senate and fill rQ and dQ with respective indices.
While both queues are non-empty:
- Pop the front senator from each queue.
- Compare their indices.
- The one with the lower index bans the other and is added back to its queue with index +n.
When one queue is empty, the other party is the winner.

Java Code

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

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

        while (!rQ.isEmpty() && !dQ.isEmpty()) {
            int ri = rQ.poll();
            int di = dQ.poll();
            if (ri < di) {
                rQ.add(ri + n);
            } else {
                dQ.add(di + n);
            }
        }

        return rQ.size() > dQ.size() ? "Radiant" : "Dire";
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	`O(n)` per round, worst-case `O(n log n)` total
Space Complexity	`O(n)`
Explanation	Each senator is added/removed from queue log(n) times

Dry Run

Input:

senate = "RDD"

Initial Queues:

rQ = [0]
dQ = [1, 2]

Round Simulation:

r = 0, d = 1 → 0 < 1 → R bans D at index 1 → rQ = [3], dQ = [2]
r = 3, d = 2 → 2 < 3 → D bans R at index 3 → rQ = [], dQ = [6]

Winner: Dire

Conclusion

This is a queue-based turn simulation problem that requires careful management of indices and round progression. It teaches:

Queue-based state simulation
Index manipulation for cyclic turn simulation