Dota2 Senate

Difficulty: Medium Source: NeetCode

Problem

In Dota2’s world, there are two parties: Radiant (R) and Dire (D). The senate is a string of Rs and Ds. In each round, senators take turns in the order they appear in the string. Each senator can ban one senator from the opposing party (removes them from all future rounds). Once only one party’s senators remain, that party announces victory. Return the name of the winning party ("Radiant" or "Dire").

Example 1: Input: senate = "RD" Output: "Radiant" Explanation: R bans D, R wins.

Example 2: Input: senate = "RDD" Output: "Dire" Explanation: R bans first D, second D bans R, second D wins.

Constraints:

• 1 <= senate.length <= 10^4
• senate[i] is 'R' or 'D'

Prerequisites

Before attempting this problem, you should be comfortable with:

• Queues — simulating turns in order
• Greedy algorithms — always ban the next opponent, not a random one

1. Brute Force — Repeated Simulation

Intuition

Simulate the rounds. In each round, go through the senate string. Each senator gets a “banning token”. If a senator has an available token and there’s an opponent, use the token to ban the next opponent. Repeat until one party is gone.

Algorithm

1. Represent the senate as a list.
2. In each round, track available bans per party.
3. Remove banned senators.
4. Repeat until only one party remains.

Solution

def predictPartyVictory(senate):
    senate = list(senate)

    while True:
        radiant_bans = 0
        dire_bans = 0
        next_senate = []

        for senator in senate:
            if senator == 'R':
                if dire_bans > 0:
                    dire_bans -= 1  # this R gets banned
                else:
                    radiant_bans += 1
                    next_senate.append('R')
            else:
                if radiant_bans > 0:
                    radiant_bans -= 1  # this D gets banned
                else:
                    dire_bans += 1
                    next_senate.append('D')

        senate = next_senate
        if all(s == 'R' for s in senate):
            return "Radiant"
        if all(s == 'D' for s in senate):
            return "Dire"


print(predictPartyVictory("RD"))    # Radiant
print(predictPartyVictory("RDD"))   # Dire
print(predictPartyVictory("RDDRD")) # Radiant

Complexity

• Time: O(n²) — each round might only eliminate one senator
• Space: O(n)

2. Greedy — Two Queues of Indices

Intuition

The greedy insight: when a senator acts, they should always ban the next opponent (the one with the smallest index among remaining opponents). This maximises their advantage — banning a later opponent leaves an earlier opponent free to act first next round.

Use two queues: one for Radiant senator indices, one for Dire. Each round, pop from both queues. The senator with the smaller index acts first and bans the other. The winner re-queues at index + n (to represent being at the back of the next round). Repeat until one queue is empty.

Algorithm

1. Build radiant queue and dire queue of indices.
2. While both queues are non-empty:
   • Pop r = radiant.popleft() and d = dire.popleft().
   • Smaller index wins and re-queues at + n.
3. Return "Radiant" if radiant queue is non-empty, else "Dire".

Solution

from collections import deque

def predictPartyVictory(senate):
    n = len(senate)
    radiant = deque()
    dire = deque()

    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)

    while radiant and dire:
        r = radiant.popleft()
        d = dire.popleft()

        # Smaller index acts first and survives into the next round
        if r < d:
            radiant.append(r + n)  # re-queue at the back
        else:
            dire.append(d + n)

    return "Radiant" if radiant else "Dire"


print(predictPartyVictory("RD"))        # Radiant
print(predictPartyVictory("RDD"))       # Dire
print(predictPartyVictory("RDDRD"))     # Radiant
print(predictPartyVictory("RRDD"))      # Radiant
print(predictPartyVictory("DRRR"))      # Radiant

Complexity

• Time: O(n)
• Space: O(n)

Common Pitfalls

Not re-queuing the winner with offset + n. After a senator bans an opponent, they’re still active next round. By appending index + n, we ensure the senator stays at the “end” relative to senators with original indices — correctly simulating their position in the next round’s order.

Randomly choosing which opponent to ban. The optimal strategy is always to ban the opponent who would act soonest (smallest remaining index). The two-queue approach enforces this automatically.

Stopping too early. The simulation ends when one queue is completely empty. Don’t stop at the end of a single round — senators in queues might still have more rounds to act.