649. Dota2 Senate
Medium · solved 2026-10-05 · Open on LeetCode
queuegreedystring
Time O(n) · Space O(n)
How to get there
Ban the rival who votes next
1. Decide whom to ban. Every rival still in the vote will get a turn and ban one of yours, unless banned first. The rival whose turn comes soonest strikes first, so ban that one. On RDRDD, R0 bans D1 and R2 bans D3, so neither gets a turn. D4 then bans R0, and in the next round R2 bans D4: Radiant wins, two against three. If R0 bans D4 instead, D1 votes right away and bans R2, and Dire wins.
2. Run it by hand and find where one pass gets stuck. In that run D4 bans R0, who already voted this round, and R2 votes a second time. The vote goes round until one party is gone. Each ban has to find its target by looking ahead past the senators already banned, wrapping round the end: up to n steps per ban.
3. Find what a ban has to remember. A ban only says that the next senator of that party to come up loses their turn. So it needs no target yet: count it, bans["D"] += 1, and settle it when a Dire senator comes up. Whoever comes up while their party has a ban waiting is exactly the senator it was meant for. Bans against one party are interchangeable, so one count per party is enough.
4. Let the turn order pick the data structure. Senators who keep their vote take turns in the same order every round: the one at the front votes, then waits behind everyone else. First in, first out: a queue. Pop the front, then append a senator who voted and drop one who was banned.
5. Decide when to stop. Once a party has no senators left, the other side wins. Count each party’s senators and stop when one count reaches zero.
6. Check the cost. Each turn either removes a senator, at most n times in all, or casts a ban that removes one later. On every senate of up to 14 senators the vote ends within 2n turns, so the time is O(n), and the queue takes O(n) space.
The reusable recipe: when players take turns in a fixed cycle, keep them in a queue, popping the front and appending them back while they are still in. When an action hits “the next one of a kind”, count it as pending and settle it when that kind comes up.
Let the counts' meanings write the branches
| Variable | Always means, at the top of the loop |
|---|---|
queue |
the senators still in the vote, in the order of their next turns |
remaining[p] |
how many senators of party p are in queue |
bans[p] |
bans cast on party p and not yet applied: the next bans[p] senators of p to come up are out |
A senator is stored as their party’s letter, "R" or "D", since two senators of one party are interchangeable. The vote is decided once a party has no senators left, so the loop runs while remaining["R"] and remaining["D"].
Every turn starts the same way: senator = queue.popleft() takes the front, and rival names the other party. Then each case is the smallest change that keeps the meanings true:
| Case | What it means | What must change | Code |
|---|---|---|---|
bans[senator] > 0 |
this senator is the one a waiting ban was meant for | the ban is used up, and the senator stays out of queue |
bans[senator] -= 1, remaining[senator] -= 1 |
| no ban waiting | this senator votes | the next rival to come up loses their turn, and this senator votes again next round | bans[rival] += 1, queue.append(senator) |
When the loop stops, the party with senators left is the answer.
deque comes from collections. LeetCode imports it for you; running this file elsewhere needs from collections import deque at the top.
The method carries over: write down what each variable always means, then make each case the smallest update that keeps every meaning true.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| Search for each ban’s target | O(n²) | O(n) | Mark senators as banned; on each vote, scan ahead, wrapping round the end, for the next rival still in. |
| Two queues of turn positions | O(n) | O(n) | One queue per party holds each senator’s position. The earlier of the two fronts bans the later one and rejoins its queue at position + n. |
One queue, ban counts (chosen, solution-2-clean.py) |
O(n) | O(n) | Pop the front: a waiting ban removes the senator, otherwise they ban the next rival and go to the back. Stop when a party has no senators left. |
One queue, ban counts, stop past n (solution-1-original.py) |
O(n) | O(n) | The same turns, stopping once a ban count exceeds len(senate). |
A ban count exceeds n only after its party is gone, while the survivors keep voting and banning an empty party, so solution-1-original.py returns the same winner after at most n + 1 extra turns. The two-queue version removes one senator per comparison, so it ends within n comparisons. The chosen version needs no comparison, because each ban waits for the next rival to come up.
solution-1-original.py
class Solution:
def predictPartyVictory(self, senate: str) -> str:
# ban_r: 0, ban_d: 0, queue: [R, R, D, D, D]
# ban_r: 0, ban_d: 1, queue: [R, D, D, D, R]
# ban_r: 0, ban_d: 2, queue: [D, D, D, R, R]
# ban_r: 0, ban_d: 1, queue: [D, D, R, R]
# ban_r: 0, ban_d: 0, queue: [D, R, R]
# ban_r: 1, ban_d: 0, queue: [R, R, D]
# ban_r: 0, ban_d: 0, queue: [R, D]
# ban_r: 0, ban_d: 1, queue: [D, R]
# ban_r: 0, ban_d: 0, queue: [R]
ban_r = ban_d = 0
queue = deque([senator for senator in senate])
while True:
if ban_r > len(senate) or ban_d > len(senate):
break
if queue[0] == "R":
if ban_r > 0:
queue.popleft()
ban_r -= 1
else:
queue.popleft()
queue.append("R")
ban_d += 1
elif queue[0] == "D":
if ban_d > 0:
queue.popleft()
ban_d -= 1
else:
queue.popleft()
queue.append("D")
ban_r += 1
if queue[0] == "R":
return "Radiant"
else:
return "Dire"solution-2-clean.py
class Solution:
def predictPartyVictory(self, senate: str) -> str:
remaining = {"R": senate.count("R"), "D": senate.count("D")}
bans = {"R": 0, "D": 0}
queue = deque(senate)
while remaining["R"] and remaining["D"]:
senator = queue.popleft()
rival = "D" if senator == "R" else "R"
if bans[senator]:
bans[senator] -= 1
remaining[senator] -= 1
else:
bans[rival] += 1
queue.append(senator)
return "Radiant" if remaining["R"] else "Dire"Notes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.