{ }SolveLogs
⌕
Home / Greedy / #649
LeetCode #649 Medium

Dota2 Senate

Dota2 Senate is LeetCode 649 (Medium). The string senate lists senators in seat order: 'R' belongs to the Radiant party and 'D' to the Dire party. Senators speak one at a time in seat order, round after round, and a banned senator never speaks again. On their turn, a senator may:

  • ban one senator of the other party, or
  • announce victory, if every senator still in the game belongs to their own party.

Every senator plays the best strategy for their party. Return "Radiant" or "Dire", whichever party announces victory.

Constraints
  • n == senate.length
  • 1 <= n <= 10⁴
  • senate[i] is either 'R' or 'D'.
stringgreedyqueue
Open on LeetCode ↗
02

Intuition

On your turn, one opponent will speak before all the others: the first opponent after you in speaking order, counting into the next round if needed. That opponent is the one who can hurt your party soonest, so ban them. Banning a later opponent leaves the nearer one free to ban one of your senators first, and gains nothing in exchange.

With every move fixed, the game is a simulation. Give each senator a turn number, starting with their seat. Of the two parties' next speakers, the smaller turn number speaks first and bans the other. The speaker then takes a new turn number in the next round.

How to spot this pattern

Players who act in a fixed cycle and drop out one by one point to a queue: the front is whoever acts next, and anyone who survives goes to the back. Two competing sides means two queues, compared front to front.

03

Approach

Try it first

Before reading on: play "DDRRR" by hand, with every senator banning the next opponent due to speak. Who wins, and why does having more seats not help? Then decide what number a surviving senator should carry into the next round so that a single comparison still finds the next speaker. Aim for O(n).

1

Split the seats into two queues

Put the seat numbers of the 'R' senators in one queue and those of the 'D' senators in another, in seat order. The front of each queue is the next senator from that party to speak.

2

Let the earlier front ban the other

Pop both fronts. The smaller turn number speaks first, and the other front is exactly the opponent due to speak soonest, so that senator is banned. A banned senator is simply never pushed back.

3

Send the speaker to the next round

Push the speaker back onto its own queue with turn number + n. That places it after everyone still waiting in the current round, and senators who rejoin keep the same order they spoke in.

4

Stop when one queue is empty

Loop while both queues have senators. When one empties, every senator left belongs to the other party, and its next speaker announces victory, so return that party's name.

04

Dota2 Senate solution in Python | C++ | Java

▶1from collections import deque
▶2 
▶3class Solution:
▶4 def predictPartyVictory(self, senate: str) -> str:
▶5 n = len(senate)
▶6 radiant = deque(i for i, s in enumerate(senate) if s == "R")
▶7 dire = deque(i for i, s in enumerate(senate) if s == "D")
▶8 while radiant and dire:
▶9 r = radiant.popleft()
▶10 d = dire.popleft()
▶11 if r < d:
▶12 radiant.append(r + n)
▶13 else:
▶14 dire.append(d + n)
▶15 return "Radiant" if radiant else "Dire"
senateRseat 0Dseat 1Dseat 2radiant queue (turn)0seat 0dire queue (turn)1seat 12seat 2queue each seat by party, in seat order
Radiant turns0
Dire turns1, 2
Each senator's turn number starts as their seat number, so the smallest number in either queue is the next senator to speak. The front of each queue is the next speaker from that party. Every speaker bans the next opponent due to speak: that opponent is the one who would otherwise ban one of their own party first.
senateRseat 0Dseat 1Dseat 2radiant queue (turn)0seat 0dire queue (turn)1seat 12seat 2Radiant turn 0 speaks before turn 1 → ban seat 1
Radiant front0seat 0
Dire front1seat 1
speaks firstRadiant
Compare the two fronts: turn 0 comes before turn 1, so seat 0 speaks first. The opponent who would speak soonest is the other front, seat 1, so that is who gets banned.
senateRseat 0Dseat 1Dseat 2radiant queue (turn)3seat 0dire queue (turn)2seat 2seat 1 out; seat 0 rejoins as turn 3
Radiant turns3
Dire turns2
Seat 1 leaves for good. Seat 0 is not used up: it speaks again next round, so it goes to the back of its queue as turn 3 (0 + 3). Adding 3 puts it after every senator still waiting this round, and keeps it ahead of anyone who rejoins after it.
senateRseat 0Dseat 1Dseat 2radiant queue (turn)3seat 0dire queue (turn)2seat 2Dire turn 2 speaks before turn 3 → ban seat 0
Radiant front3seat 0
Dire front2seat 2
speaks firstDire
Compare the two fronts: turn 2 comes before turn 3, so seat 2 speaks first. The opponent who would speak soonest is the other front, seat 0, so that is who gets banned.
senateRseat 0Dseat 1Dseat 2radiant queue (turn)emptydire queue (turn)5seat 2seat 0 out; seat 2 rejoins as turn 5
Radiant turnsempty
Dire turns5
Seat 0 leaves for good. Seat 2 is not used up: it speaks again next round, so it goes to the back of its queue as turn 5 (2 + 3). Adding 3 puts it after every senator still waiting this round, and keeps it ahead of anyone who rejoins after it.
senateRseat 0Dseat 1Dseat 2radiant queue (turn)emptydire queue (turn)5seat 2Radiant queue empty → Dire wins
answer"Dire"1 left standing
Every Radiant senator has been banned, so the senators left can announce victory.
05

Common pitfalls

Picking the party with more senators

✗ Wrong
if senate.count("R") >= senate.count("D"):
    return "Radiant"
return "Dire"
✓ Right
while radiant and dire:
    ...
return "Radiant" if radiant else "Dire"

Speaking order matters more than numbers. In "DDRRR", both Dire senators speak first and ban two of the three Radiant senators before any of them speaks. The last Radiant senator bans one Dire senator, the other Dire senator bans it, and Dire wins.

Rejoining with the same turn number

✗ Wrong
if r < d:
    radiant.append(r)
✓ Right
if r < d:
    radiant.append(r + n)

In "RDD", seat 0 bans seat 1 and rejoins as turn 0 instead of 3. Turn 0 still looks earlier than seat 2, so seat 0 speaks twice in one round and the code returns "Radiant". In the real game seat 2 speaks next, bans seat 0, and Dire wins.

06

Edge cases

Every senator in one party, such as "RRR"

The Dire queue starts empty, so the loop never runs and the first Radiant senator announces victory: "Radiant".

07

Complexity

Time
O(n)
Space
O(n)
Each pass through the loop bans one senator for good, so there are at most n − 1 passes, each O(1). Together the two queues hold n turn numbers.
08

Dota2 Senate FAQ

Can the turn numbers overflow?

No. Each pass bans one senator, so a senator can rejoin at most n − 1 times, and every rejoin adds n. No turn number reaches n², which for n = 10⁴ is 10⁸, well inside a 32-bit integer.

Is there a way to solve it without two queues?

Yes. Walk the senate as one growing list and keep a running count of bans waiting to land on each party. A senator who is owed a ban is skipped; any other senator adds a pending ban against the other party and is appended to the end for the next round. It is also O(n), but the two queues make the speaking order easier to follow.

← Prev · #648
Replace Words
Next · #653 →
Two Sum IV — Input is BST