Dota2 Senate — Solution

Problem

In the Dota2 senate, senators from two parties — Radiant ('R') and Dire ('D') — take turns in the given order, and each may permanently revoke any one opposing senator's voting rights. A party wins when only its members retain the right to vote. Given the initial seating order as a string, determine which party wins when every senator plays optimally.

• Input: senate = "RDD"
• Output: "Dire"
• Explanation: R(0) bans D(1), but D(2) then bans R(0), leaving only Dire senators.

Counter-example: "RD" returns "Radiant" — R acts first and immediately bans the only D senator before D gets a turn.

Intuition

The optimal move is always to ban the nearest upcoming opponent — eliminating a future threat is strictly better than eliminating someone who already voted, since that delays harm for zero extra benefit. Two queues naturally track each party's "next available" senator in order, and a simple comparison of their indices decides who acts first each step.

Solution — Two-Queue Greedy

Pop the front senator from each party's queue. The one with the smaller index acts earlier in the current cycle and eliminates the other. The winner re-enters their queue at index + n, representing their slot in the next cycle.

1. Build two queues — radiant and dire — holding each party's senate indices in order.
2. While both queues are non-empty, pop the front index from each.
3. If the Radiant index is smaller, R acts first and eliminates D — re-enqueue R at r_index + n.
4. Otherwise, D acts first and eliminates R — re-enqueue D at d_index + n.
5. The party with a non-empty queue when the loop ends declares victory.

1from collections import deque
2
3def predictPartyVictory(senate: str) -> str:
4    n = len(senate)
5    radiant = deque(i for i, c in enumerate(senate) if c == 'R')
6    dire = deque(i for i, c in enumerate(senate) if c == 'D')
7
8    while radiant and dire:
9        r_index = radiant.popleft()
10        d_index = dire.popleft()
11        if r_index < d_index:
12            radiant.append(r_index + n)  # R acts first; survives to next cycle
13        else:
14            dire.append(d_index + n)  # D acts first; survives to next cycle
15
16    return "Radiant" if radiant else "Dire"

Time: O(n) — each senator is eliminated exactly once; total loop iterations equal the number of senators eliminated, which is at most n − 1.
Space: O(n) — two queues together hold at most n entries at any time.

Complexity Summary

Common Mistakes

• Forgetting + n when re-enqueuing the winner — without adding n, the winning senator gets an index smaller than any remaining senator, making them always act first in subsequent comparisons and breaking cycle ordering entirely.
• Comparing party sizes instead of indices — a party with more senators does not automatically win; the voting order determines outcomes, not headcount.
• Re-initializing queues at the start of each round — the + n trick handles multi-round cycling implicitly; there is no need to restart between rounds.
• Swapping the return values — after the loop, the non-empty queue is the winner; when dire is empty, return "Radiant", not the reverse.
• Using a Python list with pop(0) instead of a deque — list.pop(0) is O(n) per call, turning the whole algorithm O(n²); always use collections.deque for queue operations in Python.

Related Problems

• Asteroid Collision — two groups of opposing elements eliminate each other in sequence using greedy stack logic
• Gas Station — greedy circular simulation to find a starting point where resources never run dry
• Reveal Cards In Increasing Order — queue simulation to reconstruct a specific card-reveal ordering
• Remove K Digits — greedy elimination using a monotonic structure to minimize the resulting number