LeetCode 649 - Dota2 Senate

The problem describes a turn-based voting process between two parties in the Dota2 senate, the Radiant party represented by 'R' and the Dire party represented by 'D'. We are given a string senate where each character represents a senator and their party affiliation.

leetcodemediumstringgreedyqueue

LeetCode Problem 649

Difficulty: 🟡 Medium
Topics: String, Greedy, Queue

Solution

Problem Understanding

The problem describes a turn-based voting process between two parties in the Dota2 senate, the Radiant party represented by 'R' and the Dire party represented by 'D'.

We are given a string senate where each character represents a senator and their party affiliation. The order of characters in the string is important because senators act sequentially from left to right in each round.

Each active senator has two possible actions:

  1. Ban one opposing senator so that the banned senator loses all future voting rights.
  2. Declare victory if all remaining active senators belong to the same party.

The process repeats in rounds until one party completely eliminates the other party's ability to act.

The key detail is that every senator acts optimally for their own party. This means each senator will always choose the action that maximizes their party’s chance of winning. In practice, this means senators will strategically ban opponents whenever possible.

The input size can be as large as 10^4, which is large enough that repeatedly simulating the senate using expensive operations like removing characters from strings or scanning for the next active senator could become inefficient.

The expected output is simply:

  • "Radiant" if the Radiant party eventually wins
  • "Dire" if the Dire party eventually wins

Several edge cases are important to recognize early:

  • A senate with only one senator, such as "R" or "D", immediately results in victory for that party.
  • Alternating patterns like "RDRDRD" create many rounds of interaction and test whether the simulation preserves ordering correctly.
  • Large blocks like "RRRRDDDD" test whether the algorithm efficiently handles repeated bans.
  • Cases where one party gains an early positional advantage are critical because acting earlier in the round often determines the winner.

The problem guarantees that every character is either 'R' or 'D', so there is no need for input validation beyond the algorithm itself.

Approaches

Brute Force Simulation

A straightforward approach is to simulate the process exactly as described.

We can maintain a list of active senators and repeatedly process them from left to right. When a senator acts, they search for the next available opponent and ban them. Banned senators are skipped in future rounds.

This method is conceptually simple because it mirrors the rules directly. However, it becomes inefficient because finding the next valid opponent may require scanning through the list repeatedly. Removing senators or marking them inactive also introduces overhead.

In the worst case, every senator may repeatedly scan through nearly the entire senate list across many rounds. This leads to quadratic time complexity or worse.

Although the brute-force simulation produces the correct result, it is too slow for larger inputs near the upper constraint limit.

Optimal Queue-Based Greedy Simulation

The key insight is that the only thing that matters is the relative order in which senators act.

Instead of explicitly simulating rounds and removing senators, we can track the positions of active senators from both parties using queues.

The idea works like this:

  • Store the indices of all Radiant senators in one queue.
  • Store the indices of all Dire senators in another queue.
  • Compare the front senator from each queue.
  • The senator with the smaller index acts first because they appear earlier in the current round.
  • That senator bans the opposing senator.
  • The surviving senator is re-added to the queue with index current_index + n, representing participation in the next round.

This efficiently preserves turn order without repeatedly rebuilding the senate state.

The greedy observation is that acting earlier is always optimal because banning an opponent prevents them from acting at all.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeated scanning and banning operations
Optimal O(n) O(n) Queue simulation preserves ordering efficiently

Algorithm Walkthrough

  1. Create two queues, one for Radiant senators and one for Dire senators.

Each queue stores the indices of senators from that party. For example, for "RDD", the Radiant queue starts as [0] and the Dire queue starts as [1, 2]. 2. Traverse the input string once.

For every character:

  • If the character is 'R', append its index to the Radiant queue.
  • If the character is 'D', append its index to the Dire queue.

This preprocessing step separates senators by party while preserving their original order. 3. Start simulating rounds while both queues are non-empty.

As long as both parties still have active senators, the voting process continues. 4. Remove the front senator from both queues.

These are the next active senators from each party.

  • The smaller index acts first because senators act in order.
  • The senator who acts first bans the opposing senator.
  1. Reinsert the surviving senator into their queue.

Suppose the senate length is n.

  • If the Radiant senator acted first, append radiant_index + n to the Radiant queue.
  • If the Dire senator acted first, append dire_index + n to the Dire queue.

Adding n simulates that senator participating again in the next round after all current senators have had their turns. 6. Repeat until one queue becomes empty.

If the Radiant queue becomes empty, Dire wins.

If the Dire queue becomes empty, Radiant wins.

Why it works

The algorithm maintains the invariant that queues always represent the correct future action order for each party.

At every step, the senator with the smaller index acts first and bans the opposing senator before they can act. Re-adding the surviving senator with index index + n correctly places them at the end of the future turn order.

Because every senator always benefits from banning the next available opponent immediately, the greedy choice is optimal. Eventually, one party completely eliminates the other party's ability to act.

Python Solution

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)

        radiant_queue = deque()
        dire_queue = deque()

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

        while radiant_queue and dire_queue:
            radiant_index = radiant_queue.popleft()
            dire_index = dire_queue.popleft()

            if radiant_index < dire_index:
                radiant_queue.append(radiant_index + n)
            else:
                dire_queue.append(dire_index + n)

        return "Radiant" if radiant_queue else "Dire"

The implementation begins by importing deque from the collections module because queues require efficient removal from the front. Using a regular Python list would make front removals expensive.

The variable n stores the senate length. This value is later used when reinserting surviving senators into future rounds.

The first loop processes the senate string once and distributes senator indices into the appropriate queues. This preserves the original turn order.

The main simulation loop continues while both parties still have active senators.

Inside the loop:

  • The front senator from each queue is removed.
  • Their indices are compared.
  • The senator with the smaller index acts first and survives.
  • The surviving senator is reinserted with index + n, placing them into the next cycle of turns.

Once one queue becomes empty, the remaining party is declared the winner.

Go Solution

func predictPartyVictory(senate string) string {
	n := len(senate)

	radiantQueue := []int{}
	direQueue := []int{}

	for i, senator := range senate {
		if senator == 'R' {
			radiantQueue = append(radiantQueue, i)
		} else {
			direQueue = append(direQueue, i)
		}
	}

	for len(radiantQueue) > 0 && len(direQueue) > 0 {
		radiantIndex := radiantQueue[0]
		direIndex := direQueue[0]

		radiantQueue = radiantQueue[1:]
		direQueue = direQueue[1:]

		if radiantIndex < direIndex {
			radiantQueue = append(radiantQueue, radiantIndex+n)
		} else {
			direQueue = append(direQueue, direIndex+n)
		}
	}

	if len(radiantQueue) > 0 {
		return "Radiant"
	}

	return "Dire"
}

The Go implementation follows the same logic as the Python version.

Since Go does not have a built-in deque structure in the standard library, slices are used as queues. The front element is accessed with index 0, and removal is simulated using slice re-assignment with queue = queue[1:].

Integer overflow is not a concern because the maximum senate size is only 10^4, and the indices grow linearly during the simulation.

Go strings are iterable as runes, but since the input contains only ASCII characters 'R' and 'D', direct comparison works safely.

Worked Examples

Example 1

Input:

senate = "RD"

Initial queues:

Party Queue
Radiant [0]
Dire [1]

First iteration:

Radiant Index Dire Index Earlier Senator Result
0 1 Radiant Dire senator banned

Radiant survives and is re-added with index 0 + 2 = 2.

Updated queues:

Party Queue
Radiant [2]
Dire []

The Dire queue is empty, so Radiant wins.

Output:

"Radiant"

Example 2

Input:

senate = "RDD"

Initial queues:

Party Queue
Radiant [0]
Dire [1, 2]

First iteration:

Radiant Index Dire Index Earlier Senator Result
0 1 Radiant Dire senator banned

Radiant survives and is re-added with index 0 + 3 = 3.

Updated queues:

Party Queue
Radiant [3]
Dire [2]

Second iteration:

Radiant Index Dire Index Earlier Senator Result
3 2 Dire Radiant senator banned

Dire survives and is re-added with index 2 + 3 = 5.

Updated queues:

Party Queue
Radiant []
Dire [5]

Radiant has no remaining senators, so Dire wins.

Output:

"Dire"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each senator enters and leaves the queue a limited number of times
Space O(n) Queues store senator indices

The algorithm is linear because every senator is processed through queue operations that each take constant time.

Although senators may be reinserted multiple times, every iteration removes one opposing senator permanently. Since there are only n senators total, the total number of iterations is bounded by n.

The space complexity is also linear because both queues together store at most n indices.

Test Cases

solution = Solution()

assert solution.predictPartyVictory("RD") == "Radiant"  # Simple Radiant win
assert solution.predictPartyVictory("RDD") == "Dire"  # Example where Dire recovers
assert solution.predictPartyVictory("R") == "Radiant"  # Single Radiant senator
assert solution.predictPartyVictory("D") == "Dire"  # Single Dire senator
assert solution.predictPartyVictory("RRRR") == "Radiant"  # All Radiant senators
assert solution.predictPartyVictory("DDDD") == "Dire"  # All Dire senators
assert solution.predictPartyVictory("RDRD") == "Radiant"  # Alternating pattern
assert solution.predictPartyVictory("DRDR") == "Dire"  # Alternating starting with Dire
assert solution.predictPartyVictory("RRDDD") == "Radiant"  # Early positional advantage
assert solution.predictPartyVictory("DDRRR") == "Dire"  # Dire acts first repeatedly
assert solution.predictPartyVictory("RDDRRDRD") in ["Radiant", "Dire"]  # Larger mixed case
Test Why
"RD" Smallest competitive example
"RDD" Demonstrates multiple rounds
"R" Single senator boundary case
"D" Single senator boundary case
"RRRR" Only one party exists
"DDDD" Only one party exists
"RDRD" Alternating turn order
"DRDR" Alternating with opposite starting advantage
"RRDDD" Tests positional advantage
"DDRRR" Tests repeated early bans
"RDDRRDRD" Larger mixed simulation

Edge Cases

One important edge case is when the senate contains only one senator, such as "R" or "D". A naive implementation might still attempt to simulate rounds or access an empty queue after banning operations. The queue-based solution handles this naturally because one queue starts empty immediately, so the algorithm terminates without entering the simulation loop.

Another important case is when all senators belong to the same party, such as "RRRR" or "DDDD". Some implementations incorrectly assume both parties are always present. In this solution, one queue remains empty after initialization, so the winner is returned immediately.

Alternating patterns like "RDRDRDRD" are another common source of bugs because they require careful maintenance of turn order across multiple rounds. If indices are not reinserted correctly using index + n, senators may act in the wrong sequence. The queue approach preserves the exact future ordering by treating the senate as a cyclic structure.

A subtler edge case involves positional advantage. Consider "RDD". Even though the parties are nearly balanced, the earlier Dire senator eventually gains control because of turn order dynamics. A naive counting-based solution that only compares party sizes would fail here. The queue simulation correctly models that acting earlier is often more important than having equal numbers.