algoadvance

In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties. Now the senate wants to ban each other’s members. The Dota2 game has a simple rule for banning:

  1. Every senator can exercise one “ban” per round.
  2. Only one party can exercise a “ban” at a time, and once a senator decides to “ban” a senator from the other party, this “ban” takes immediate effect, and the banned senator will be out of the senate and lose all his rights in this and subsequent rounds.
  3. Each senator’s turn in the senate follows a circular order. After the last senator’s turn, it goes back to the first senator, and so on.

Given a string senate representing each senator’s party, determine which party will eventually ban the other party’s senators and win. The output should be “Radiant” if the Radiant party will win and “Dire” if the Dire party will win.

Clarifying Questions

  1. Will there always be at least one senator from each party at the beginning?
    • Yes, there will be at least one senator from both parties according to the problem description.
  2. Can the string contain any other characters besides ‘R’ and ‘D’?
    • No, the string will only contain ‘R’ (Radiant) and ‘D’ (Dire).
  3. Is the length of the string within a reasonable limit (e.g., could it be extremely large)?
    • Yes, typically for LeetCode problems, the constraints are such that the length is within typical problem-solving scopes, e.g., up to 10^4.

Strategy

We’ll use a queue-based approach to solve the problem. The main idea is to simulate the banning process, where each senator gets their turn, and each time one senator bans an opposing senator, that senator is effectively removed from the competition. The queue helps in maintaining the circular order:

  1. Initialize two queues, one for Radiant and one for Dire senators. Each queue stores the indices of the senators in the order they appear in the senate string.
  2. Loop while both queues are not empty:
    • Extract the first senator (front) of each queue.
    • Compare their indices to determine who gets to ban whom.
    • The winning senator stays in the game and moves to the end of the queue (with index incremented by the length of the senate string).
  3. The remaining non-empty queue determines the winning party.

Code

from collections import deque

def predictPartyVictory(senate: str) -> str:
    radiant = deque()
    dire = deque()
    
    for i, s in enumerate(senate):
        if s == 'R':
            radiant.append(i)
        else:
            dire.append(i)
    
    n = len(senate)
    
    while radiant and dire:
        r_idx = radiant.popleft()
        d_idx = dire.popleft()
        
        if r_idx < d_idx:
            radiant.append(r_idx + n)
        else:
            dire.append(d_idx + n)
    
    return "Radiant" if radiant else "Dire"

# Example usage:
senate = "RDD"
print(predictPartyVictory(senate))  # Output: "Dire"

Time Complexity

  1. Initialization of queues: O(n), where n is the length of the senate string.
  2. While loop (processing rounds): Each round involves dequeuing and enqueuing operations, making it O(n) in total because each senator enqueues at most once after its initial placement.

Overall Complexity: O(n)

This complexity is efficient and feasible for typical input sizes constrained by LeetCode.

Try our interview co-pilot at AlgoAdvance.com