Dota2 Senate
Simulate the Dota2 senate vote with two queues of turns: whichever senator acts first bans the other and rejoins its queue for the next round.
Problem Understanding
Dota2 Senate (LeetCode 649): the senate is a string of R (Radiant) and D (Dire) senators. Voting goes round by round in seat order, and each senator still in play can ban one senator of the other party, removing them for good. Banned senators are skipped. As soon as everyone left belongs to one party, that party announces victory. Assuming every senator plays optimally for their party, return "Radiant" or "Dire".
Examples: "RD" → Radiant; "RDD" → Dire.
The Intuition: Ban the Next Threat
When it is your turn, the opponent who will act next is the one about to ban one of your senators. Banning them is always at least as good as banning anyone else. With that greedy rule, the game becomes a simulation.
- Two queues of turns, one per party, in seat order.
- Duel the fronts. The smaller turn number acts first and bans the other.
- The winner votes again next round. Push it back with turn + n, so it sorts after the rest of this round.
It is a greedy choice made safe by an exchange argument, like the ones in Greedy Algorithms, simulated with a queue as in Number of Recent Calls.
Interactive Walkthrough
3 SEATS · TURN ≥ 3 = NEXT ROUND
QUEUE THE SEATS
senate (seat numbers below)
0
1
2
Radiant queue
front
Dire queue
front
Radiant left
1
Dire left
2
Winner
:
Queue each party's seats in voting order: Radiant [0], Dire [1, 2]
Next
Next up: Radiant turn 0 (seat 0) against Dire turn 1 (seat 1). The earlier turn acts first
senate
The top row is the senate; banned seats are struck through. Below, each party's queue of turns, front on the left. The two turns facing off are drawn in front of their queues: green acts first, red is banned. Try Outnumbered to see the smaller party win.
Dry Run Table
Input: senate = "RDD", n = 3. Radiant [0], Dire [1, 2].
| Duel | Radiant turn | Dire turn | Result | Radiant | Dire |
|---|---|---|---|---|---|
| 1 | 0 | 1 | R0 bans D1, rejoins as 3 | [3] | [2] |
| 2 | 3 | 2 | D2 bans R0, rejoins as 5 | [] | [5] |
The Radiant queue is empty. Answer: "Dire".
The Solution Template
Two queues of turn numbers and a loop of duels. The JavaScript, TypeScript and C versions use arrays with front indices as queues.
Dota2 Senate Code
1var predictPartyVictory = function(senate) {2 const n = senate.length;3 const radiant = [], dire = [];4 for (let i = 0; i < n; i++) {5 if (senate[i] === 'R') radiant.push(i);6 else dire.push(i);7 }8 let rf = 0, df = 0;9 while (rf < radiant.length && df < dire.length) {10 const r = radiant[rf++], d = dire[df++];11 if (r < d) {12 radiant.push(r + n);13 } else {14 dire.push(d + n);15 }16 }17 return rf < radiant.length ? "Radiant" : "Dire";18};
Edge Cases & Common Mistakes
- One party only: the other queue starts empty, so that party wins at once.
- Banning the first opponent in seat order: it must be the next one due to act, which may come after you in the string or wrap around to the next round.
- Forgetting + n: a senator pushed back with its old index would be compared as if it acted again in the same round.
- Counting senators instead of simulating: the larger party can lose, as
"DDRRR"shows.
Summary
Each senator bans the next opponent due to act. Keep both parties' turns in queues, let the smaller front ban the other and rejoin with turn + n, and stop when a queue empties. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet