Dota2 Senate: Greedy Voting with Two Queues

In the Dota2 world, two parties compete for control of the senate: Radiant and Dire. Each senator can either ban an opposing senator or, if all remaining senators belong to one party, declare victory. The twist is that senators act in the order they appear in the input string, and each one will always ban the closest upcoming opponent. Your job is to determine which party eventually wins. This is LeetCode 649: Dota2 Senate.

Why this problem matters

Dota2 Senate is a clean example of greedy simulation with queues. The problem looks like it might need complex round-by-round tracking, but it collapses into a simple loop once you realize two things: each senator should ban the nearest future opponent (greedy choice), and two queues perfectly model the turn order across rounds. This pattern of using queues to simulate a process where elements cycle back around appears in scheduling, round-robin, and other turn-based problems.

The approach

The key insight is that each senator always wants to ban the nearest opposing senator who has not yet acted. Why? Because letting a closer opponent act means they could ban you first. The greedy choice is always to neutralize the nearest threat.

Two queues make this clean. One holds the indices of all Radiant senators, the other holds the indices of all Dire senators. At each step, compare the front of both queues. The senator with the smaller index acts first and bans the other. The winner re-enters the back of their queue with an increased index (original index + n) to represent their position in the next round. The loser is simply removed. When one queue empties, the other party wins.

from collections import deque

def predict_party_victory(senate: str) -> str:
    n = len(senate)
    radiant = deque()
    dire = deque()

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

    while radiant and dire:
        r = radiant.popleft()
        d = dire.popleft()
        if r < d:
            radiant.append(r + n)
        else:
            dire.append(d + n)

    return "Radiant" if radiant else "Dire"

Step-by-step walkthrough

Let's trace through a small example: senate = "RDD".

Radiant has one senator at index 0. Dire has two senators at indices 1 and 2. Each round, we compare the front of each queue. The smaller index acts first (they appear earlier in the senate string) and bans the other.

Round 1: R(0) vs D(1). Since 0 < 1, Radiant acts first and bans D(1). R re-enters at index 0 + 3 = 3. Queues become R:[3], D:[2].

Round 2: D(2) vs R(3). Since 2 < 3, Dire acts first and bans R(3). D re-enters at index 2 + 3 = 5. Queues become R:[], D:[5].

Result: Radiant's queue is empty. Dire wins.

Complexity analysis

Each senator enters and leaves the queues at most a few times before being permanently banned. The total work across all rounds is proportional to the number of senators.

Edge cases to watch for

• All same party: senate = "RRRR" or senate = "DDDD". One queue starts empty, so the answer is immediate. The loop body never executes.
• Alternating senators: senate = "RDRDRD". Each R bans the next D, each D bans the next R. The party with more senators (or the one that acts first when counts are equal) wins.
• Single senator: senate = "R" or senate = "D". The opposing queue is empty from the start. Return the lone senator's party.
• Long strings with one extra: senate = "RRDDD...". Even a single extra senator for one party can swing the outcome, because the surplus senator survives to ban again in later rounds.

The building blocks

This problem combines two reusable patterns.

1. Greedy nearest-opponent banning

Each senator's optimal move is to ban the closest opposing senator who has not yet acted. This is greedy because there is never a reason to skip a closer threat to ban a farther one. If you let the closer opponent survive, they will ban you (or one of your allies) before the farther one even gets a turn. The same "neutralize the nearest threat" logic appears in problems where agents compete in a sequence and you need to decide who to target.

2. Queue-based round simulation

Using two queues to simulate a cyclic process where participants take turns, get eliminated, or re-enter. The index-offset trick (i + n) elegantly handles round transitions without needing explicit round counters or modular arithmetic. This pattern shows up whenever you have a circular or repeating process and need to track who acts next.

From understanding to recall

The two-queue approach is elegant and short, but the details matter. You need to remember to add n (not n + 1, not 2 * n) when re-enqueueing the winner. You need to compare indices, not characters. And you need to pop from both queues on every iteration, not just one.

These small details are easy to mix up under pressure. Spaced repetition drills them into muscle memory. After a few rounds of writing this solution from scratch at increasing intervals, the pattern becomes automatic. You see "two competing groups, turn-based elimination" and the two-queue template flows out without hesitation.

Related posts

• Gas Station - Another greedy problem where a single pass through a circular structure reveals the answer
• Task Scheduler - Greedy scheduling where frequency counting drives the optimal arrangement
• Queue Reconstruction by Height - A greedy insertion problem that also relies on processing elements in a carefully chosen order

CodeBricks breaks the Dota2 Senate problem into its greedy-banning and queue-simulation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy queue problem shows up in your interview, you do not think about it. You just write it.