LC649 Dota2 Senate 🟡

This maps to the Queue pattern: "Process in order — whoever comes first gets to ban first."

1. Mindset Shift

Imagine two separate queues — one for Radiant, one for Dire — each storing the index (seating position) of active senators.

Key insight: the best strategy is always to ban the nearest opponent. In each round, compare the front of both queues. The senator with the smaller index (comes first) bans the other. The survivor re-enqueues with index + n to preserve round order.

Why add n? After round 1, survivors should go behind everyone still in the current round. Adding n ensures correct ordering across rounds.

2. The Logic — 4 Steps

Start two queues and play until one side empties:

1. Prepare — iterate senate, push each index into radiant or dire.
2. Face off — popleft the front of both queues to get r and d.
3. Ban + re-enqueue — if r < d: R bans D, re-enqueue r + n into radiant. Else: D bans R, re-enqueue d + n into dire.
4. Game over — when one queue empties, the other party wins.

3. LeetCode-Ready Code

Convert the two-queue rules into code:

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        radiant = deque()          # store indices of R senators
        dire = deque()             # store indices of D senators

        # Step 1: prepare queues
        for i, c in enumerate(senate):
            if c == "R":
                radiant.append(i)
            else:
                dire.append(i)

        # Steps 2–3: face off until one side empties
        while radiant and dire:
            r = radiant.popleft()
            d = dire.popleft()
            # smaller index comes first = gets to ban
            if r < d:
                radiant.append(r + n)   # R survives, re-enqueue for next round
            else:
                dire.append(d + n)      # D survives, re-enqueue for next round

        # Step 4: the non-empty queue wins
        return "Radiant" if radiant else "Dire"

4. Dry Run — senate = "RDD"

n = 3 · Start: senate = R0 D1 D2 · radiant = 0 · dire = 1 → 2

Left of each queue = front (acts first) · +n = send survivor to the back of the next round so they don't cut ahead of anyone still waiting this round. Answer: "Dire".

5. Edge Cases & Pitfalls

The "forgot +n" mistake — most common error:

• If you re-enqueue r instead of r + n, the survivor gets the same small index.
• They'll jump ahead of senators who haven't played this round yet — wrong order, wrong answer.

6. Time & Space Complexity

• Time O(n) — each senator is banned at most once; each comparison eliminates one person.
• Space O(n) — store every senator's index in the two queues.