Dota2 Senate in Python – LeetCode75 Explained

The Dota2 Senate problem (LeetCode75) is an interesting simulation-based challenge that requires careful handling of queues and strategic thinking. It’s a popular problem because it combines string processing, greedy decisions and queue-based simulation into a single coding exercise.

In this blog, we’ll break down the problem statement, provide examples, walk through the complete Python solution and explain the step-by-step logic behind the implementation. By the end, you’ll have a clear understanding of how to solve this problem efficiently for coding interviews and competitive programming.

Problem Statement

The Dota2 Senate consists of senators from two parties: Radiant (R) and Dire (D). Each senator can ban one senator from the opposite party during each round.

The process continues in rounds:

Senators act in the order they appear in the string.
Once a senator bans another, the banned senator cannot act in the current or future rounds.
The round repeats until all senators from one party are banned.

We must return the winning party: either "Radiant" or "Dire".

Understanding the Problem

The trick here is to realize that senators keep rotating through rounds. When a senator acts, they may ban someone from the opposite party but they themselves get pushed back to the next round.

To simulate this, we use two queues:

One queue for Radiant senators (R)
One queue for Dire senators (D)

Each senator’s index determines who acts first. After acting, the winning senator gets re-added to the queue with an updated index for the next round.

Examples

Example 1

Input: senate = "RD"
Output: "Radiant"
Explanation: Radiant acts first and bans Dire immediately.

Example 2

Input: senate = "RDD"
Output: "Dire"
Explanation:

Radiant bans one Dire.
Remaining Dire senators act next and ban Radiant.
Dire wins.

Complete Python Solution

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        radiant_queue = deque()
        dire_queue = deque()

        n = len(senate)

        for i, party in enumerate(senate):
            if party == 'R':
                radiant_queue.append(i)
            else:
                dire_queue.append(i)

        while radiant_queue and dire_queue:
            radiant_senator = radiant_queue.popleft()
            dire_senator = dire_queue.popleft()

            # The senator with the smaller index bans the other senator's right
            if radiant_senator < dire_senator:
                radiant_queue.append(radiant_senator + n)
            else:
                dire_queue.append(dire_senator + n)

        return "Radiant" if radiant_queue else "Dire"

Step-by-Step Explanation

Step 1: Initialize Queues

We create two queues: one for Radiant senators and one for Dire senators. Each senator is stored with their index.

radiant_queue = deque()
dire_queue = deque()

Step 2: Fill Queues with Senators

Loop through the string and assign senators to their respective queues.

for i, party in enumerate(senate):
    if party == 'R':
        radiant_queue.append(i)
    else:
        dire_queue.append(i)

Step 3: Simulate the Banning Process

While both queues are non-empty, pick one Radiant and one Dire senator. The senator with the smaller index acts first and bans the other.

while radiant_queue and dire_queue:
    radiant_senator = radiant_queue.popleft()
    dire_senator = dire_queue.popleft()

Step 4: Reassign Winner to Next Round

The senator who survives gets re-added to the queue with index +n (to place them in the next round).

if radiant_senator < dire_senator:
    radiant_queue.append(radiant_senator + n)
else:
    dire_queue.append(dire_senator + n)

Step 5: Declare the Winner

The last remaining queue determines the winning party.

return "Radiant" if radiant_queue else "Dire"

Time and Space Complexity

Time Complexity: O(n) → Each senator is added and removed from the queue once.
Space Complexity: O(n) → Two queues store senator indices.

Edge Cases

Input: "R" → Output: "Radiant" (only one senator).
Input: "D" → Output: "Dire" (only one senator).
Input: "RRDDD" → Output: "Dire" (Dire has more senators, Radiant eventually banned).

Real-World Applications

This problem may seem like a game but the simulation approach models real scenarios such as:

Parliament or voting simulations where members eliminate others based on order and strategy.
Queue-based task scheduling in operating systems.
Resource competition in networks where processes block each other.

Conclusion

The Dota2 Senate problem is more than just a game-based challenge – it’s a great exercise in combining queue-based simulation with greedy decision-making. By representing senators with indices and simulating their actions round by round, we can model complex interactions in a simple and efficient way.

Working through this problem not only deepens your knowledge of queues and greedy algorithms but also strengthens your ability to design simulations that mirror real-world scenarios such as voting systems, scheduling and resource competition. It’s an excellent preparation tool for coding interviews and a practical skill for solving dynamic problems in software engineering.