How do you solve Dota2 Senate?

Use two queues to store indices of Radiant and Dire senators. In each iteration, dequeue one senator from each queue and compare their indices. The senator with the smaller index bans the other and is re-enqueued with their index incremented by the senate length to simulate the next round. Continue until one queue is empty, then return the corresponding party as the winner.

What pattern does Dota2 Senate use?

The Pattern: Simulation (Queue-Based Round-Robin) The Heuristic: When simulating circular turn-based processes with elimination, maintain separate queues for competing groups and use index offsets to simulate rounds efficiently without costly removals.

Dota2 Senate | Simulation

Q: What is the time complexity of Dota2 Senate?

O(n). Each senator is enqueued and dequeued at most once per round, and the total number of rounds is bounded by the number of senators, resulting in linear time complexity.

Problem

Given a string representing senators from two parties ('R' for Radiant and 'D' for Dire), simulate the banning process where each senator can ban one opposing senator in a round-robin fashion, and return the winning party once all senators of the other party are banned.

1 ≤ senate.length ≤ 10⁴
senate consists only of characters 'R' and 'D'

Example

Input: senate = "RDD"

Output: "Dire"

Initially, Radiant senator at index 0 and Dire senators at indices 1 and 2. The Radiant senator bans the Dire senator at index 1 (the next Dire senator). The Dire senator at index 2 then bans the Radiant senator at index 0. Now only Dire senators remain, so the winner is 'Dire'.

Approach

Straightforward Solution

A naive approach simulates each round by iterating over the senate string and removing banned senators, which is O(n^2) due to repeated removals and scanning, and is inefficient for large inputs.

Core Observation

The problem models a circular queue where senators take turns banning opponents. Each senator's turn depends on the relative order of the next available opponent. The key is to simulate the process efficiently without explicitly removing elements from the string.

Path to Optimal

Preview

The insight is to track the indices of Radiant and Dire senators separately in queues. At each turn, compare the front indices of both queues to determine which senator bans the other…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two queues to store indices of Radiant and Dire senators. In each iteration, dequeue one senator from each queue and compare their indices…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each senator is enqueued and dequeued at most once per round, and the total number of rounds is bounded by the number of senators, resulting in linear time complexity.

Space

O(n)

Two queues store indices of senators from each party, each potentially holding up to n elements, leading to O(n) auxiliary space.

Solution

Python

1from collections import deque
2
3class Solution:
  def predictPartyVictory(self, senate: str) -> str:
      radiant = deque()
      dire = deque()
      n = len(senate)
8
      for i, senator in enumerate(senate):
          if senator == "R":
              radiant.append(i)
          else:
              dire.append(i)
14
      while radiant and dire:
          r = radiant.popleft()
          d = dire.popleft()
18
          if r < d:
              radiant.append(r + n)
          else:
              dire.append(d + n)
23
      return "Radiant" if radiant else "Dire"

Step-by-Step Solution

1

Separate Senators into Radiant and Dire Queues by Index

5radiant = deque()
6dire = deque()
7n = len(senate)
9for i, senator in enumerate(senate):
10    if senator == "R":
11        radiant.append(i)
12    else:
13        dire.append(i)

Objective

To initialize two queues that track the positions of Radiant and Dire senators for efficient turn simulation.

Key Insight

By storing the indices of each party's senators separately, the algorithm can simulate the banning process by comparing their order of turns directly. This avoids costly string modifications and allows efficient O(1) access to the next senator of each party.

Interview Quick-Check

Core Logic

Using two queues to track indices enables direct comparison of which senator acts first in each round.

State & Boundaries

The initial population of queues must reflect the original order of senators to preserve turn sequence.

Common Pitfalls & Bugs

Failing to separate senators by party or mixing indices would prevent correct simulation of turn order.

2

Simulate Banning Rounds by Comparing Front Senators and Re-Enqueuing Winners

To simulate the banning process by repeatedly comparing the next Radiant and Dire senators and updating their turn order.

3

Return the Winning Party Based on Remaining Senators

To determine and return the winning party after all opposing senators have been banned.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 24 Critical

return "Radiant" if radiant else "Dire"

Return the winning party based on which queue still contains senators.

The party with remaining senators after the banning process is the winner, so returning the corresponding name concludes the simulation.

Line 15 Critical

while radiant and dire:

Continue simulation while both Radiant and Dire queues have senators.

The banning process continues until one party has no remaining senators, which is the termination condition.

Line 19 Critical

if r < d:

Compare indices to determine which senator acts first.

The senator with the smaller index acts first and bans the opponent, reflecting the original turn order in the circular senate.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why does re-enqueuing the winning senator with an index offset by the senate length correctly simulate the circular order of turns?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Dota2 Senate from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Dota2 Senate drill

or drill a free problem

1	`from collections import deque`
2
3	`class Solution:`
4	`def predictPartyVictory(self, senate: str) -> str:`
5	`radiant = deque()`
6	`dire = deque()`
7	`n = len(senate)`
8
9	`for i, senator in enumerate(senate):`
10	`if senator == "R":`
11	`radiant.append(i)`
12	`else:`
13	`dire.append(i)`
14
15	`while radiant and dire:`
16	`r = radiant.popleft()`
17	`d = dire.popleft()`
18
19	`if r < d:`
20	`radiant.append(r + n)`
21	`else:`
22	`dire.append(d + n)`
23
24	`return "Radiant" if radiant else "Dire"`

5	`radiant = deque()`
6	`dire = deque()`
7	`n = len(senate)`
9	`for i, senator in enumerate(senate):`
10	`if senator == "R":`
11	`radiant.append(i)`
12	`else:`
13	`dire.append(i)`