Solution Approach

The solution uses two queues and simulation to model the voting process efficiently.

Data Structure Setup:

• Create two deques qr and qd to store the indices of Radiant and Dire senators respectively
• Iterate through the input string and populate the queues with the original indices (0 to n-1)

Simulation Process: The main loop continues while both queues have senators (while qr and qd):

1. Dequeue the front senator from each party:

   • qr[0] represents the next Radiant senator's position
   • qd[0] represents the next Dire senator's position

2. Determine who acts first by comparing indices:

   • If qr[0] < qd[0]: The Radiant senator at position qr[0] gets to act first
     • They ban the Dire senator at position qd[0]
     • The Radiant senator survives and gets re-queued with index qr[0] + n
   • If qd[0] < qr[0]: The Dire senator at position qd[0] gets to act first
     • They ban the Radiant senator at position qr[0]
     • The Dire senator survives and gets re-queued with index qd[0] + n

3. Remove both senators from the front of their queues:

   • qr.popleft() and qd.popleft() are called regardless of who won
   • The winner was already added back to their queue with an updated index

Why add n to the index? Adding n ensures that senators who survive maintain their relative ordering for future rounds. For example, if a senator at position 2 survives round 1, they become position 2 + n for round 2, which is guaranteed to be larger than any first-round positions but maintains order among second-round participants.

Determining the Winner: After the loop ends, one queue will be empty while the other still has senators. The party with remaining senators wins:

• Return "Radiant" if qr is not empty
• Return "Dire" if qd is not empty (when qr is empty)

Time Complexity: O(n) where n is the length of the senate string. Each senator can be processed at most twice. Space Complexity: O(n) for storing the two queues.

Example Walkthrough

Let's walk through the example senate = "RDDR" step by step:

Initial Setup:

• n = 4 (length of senate)
• qr = [0, 2] (Radiant senators at positions 0 and 2)
• qd = [1, 3] (Dire senators at positions 1 and 3)

Round 1, First Vote:

• Compare front senators: qr[0] = 0 vs qd[0] = 1
• Since 0 < 1, Radiant senator at position 0 acts first
• R(0) bans D(1), then gets re-queued at position 0 + 4 = 4
• Remove both from front: qr.popleft(), qd.popleft()
• State: qr = [2, 4], qd = [3]

Round 1, Second Vote:

• Compare front senators: qr[0] = 2 vs qd[0] = 3
• Since 2 < 3, Radiant senator at position 2 acts first
• R(2) bans D(3), then gets re-queued at position 2 + 4 = 6
• Remove both from front: qr.popleft(), qd.popleft()
• State: qr = [4, 6], qd = [] (empty!)

Result:

• qd is empty, meaning all Dire senators have been banned
• qr still has senators [4, 6] with voting rights
• Return "Radiant"

The key insight: Even though the original string had equal numbers of R and D senators, the Radiant senators at positions 0 and 2 got to act before the Dire senators at positions 1 and 3, allowing them to eliminate all opposition before those Dire senators could retaliate.

Time and Space Complexity

Time Complexity: O(n)

Each senator gets processed at most twice - once in their initial position and potentially once more when they're added back to the queue with index i + n. In the worst case, we might have alternating senators (like "RDRDRD..."), where each round eliminates one senator from each party. This would result in approximately n/2 rounds, and in each round, we process 2 senators. Therefore, the total number of operations is bounded by O(n).

Space Complexity: O(n)

We use two deques qr and qd to store the indices of senators. In the worst case, all senators belong to one party initially, requiring O(n) space. Even though we add indices with value i + n during processing, at any point in time, the total number of elements across both queues never exceeds n (as we remove one element for each element we add). Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Understanding Why We Add n to Indices

A common mistake is trying to use boolean flags or separate tracking arrays to mark banned senators instead of the queue-based approach with index incrementation.

Incorrect Approach:

def predictPartyVictory(self, senate: str) -> str:  banned = [False] * len(senate)  r_count = senate.count('R')  d_count = senate.count('D')   while r_count > 0 and d_count > 0:  for i in range(len(senate)):  if banned[i]:  continue  # Complex logic to find and ban next opponent...

Why it's problematic: This approach requires multiple passes through the array and complex bookkeeping to track who can still vote in each round.

Solution: Use the queue approach where adding n naturally handles the round-based ordering without extra data structures.

2. Forgetting to Remove Both Senators from Queues

A critical error is only removing the banned senator from their queue while forgetting to remove the acting senator (who gets re-added with updated index).

Incorrect Code:

while radiant_queue and dire_queue:  if radiant_queue[0] < dire_queue[0]:  dire_queue.popleft() # Only removing the banned senator  radiant_queue.append(radiant_queue[0] + senate_length)  # Missing: radiant_queue.popleft()

Why it fails: The acting senator never gets removed from the front of their queue, causing an infinite loop or incorrect simulation.

Solution: Always remove both senators from the front of their queues, regardless of who wins the confrontation:

radiant_position = radiant_queue.popleft() # Remove first dire_position = dire_queue.popleft() # Remove first # Then decide who survives and gets re-queued

3. Using Wrong Data Structure

Using a list instead of a deque leads to inefficient operations.

Inefficient Approach:

radiant_queue = [] dire_queue = [] # Later in the loop: radiant_position = radiant_queue.pop(0) # O(n) operation!

Why it's problematic: list.pop(0) is O(n) because it requires shifting all remaining elements. With multiple rounds, this creates O(n²) time complexity.

Solution: Use collections.deque which provides O(1) operations for both append() and popleft():

from collections import deque radiant_queue = deque() dire_queue = deque()

4. Misunderstanding the Greedy Strategy

Some might think each senator should ban the strongest future opponent or use complex lookahead logic.

Overthinking Example:

# Trying to find the "best" senator to ban def find_best_target(queue, positions):  # Complex logic to evaluate future threats...

Why it's wrong: The optimal strategy is simply to ban the very next opposing senator who would vote. Any other strategy allows more opposing senators to act.

Solution: Trust the greedy approach - always ban the opponent at the front of their queue (the next one to act).