Skip to main content
CodePeetCodePeet
CodePeet 250

Dota2 Senate

MEDIUMProblemSolveExternal Links

Description

In the Dota2 world, the senate is made up of senators from two parties: Radiant ('R') and Dire ('D').

The senate votes in rounds. In each round, senators act one by one in the order they appear in the string (left to right). When it is a senator's turn, they can do one of two things:

  1. Ban one senator from the opposing party — that senator loses all voting rights for the current round and all future rounds.
  2. Announce victory — if all remaining senators with voting rights belong to the same party, that party wins.

Every senator plays optimally for their own party. The process repeats in rounds (cycling back to the start of the string) until one party has no senators left.

Given a string senate where each character is 'R' or 'D', predict which party will announce victory. Return "Radiant" or "Dire".

Examples

Example 1

Input: senate = "RD"

Output: "Radiant"

Explanation: Senator 0 is Radiant and acts first. They ban senator 1 (Dire). Now only Radiant senators remain, so Radiant announces victory in round 2.

Example 2

Input: senate = "RDD"

Output: "Dire"

Explanation:

  • Round 1: Senator 0 (R) bans senator 1 (D). Senator 1 is now powerless. Senator 2 (D) bans senator 0 (R) — senator 0 loses rights for future rounds.
  • Round 2: Only senator 2 (D) has voting rights. Dire announces victory.

Constraints

  • n == senate.length
  • 1 ≤ n ≤ 10^4
  • senate[i] is either 'R' or 'D'

Editorial

Brute Force

Intuition

The most direct approach is to simulate the voting process round by round, exactly as described.

Imagine the senators sitting in a row. Each round, we walk down the row from left to right. When a senator's turn comes:

  • If they have been banned, skip them.
  • Otherwise, they ban the next opposing senator who would get to vote. The optimal strategy is always to ban the nearest future threat — the opposing senator who would act soonest.

To implement this efficiently within a round, we use a pending bans counter. When an R senator acts and no D-ban is pending against them, they 'reserve' a ban (increment r_pending). The next D senator encountered will be consumed by that pending ban. Similarly for D senators creating d_pending bans against future R senators.

Crucially, pending bans carry over between rounds. If a D senator at the end of round 1 creates a pending ban, it wraps around and takes effect on the first active R senator at the start of round 2. This models the circular nature of the voting process.

We repeat rounds until one party has zero active senators.

Step-by-Step Explanation

Let's trace through senate = "RDD".

Setup: active = [true, true, true], r_count = 1, d_count = 2, r_pending = 0, d_pending = 0.

Round 1:

Step 1: Senator 0 (R). No D-ban is pending (d_pending = 0), so R(0) is safe. R creates a pending ban: r_pending = 1. Meaning: the next D senator to act will be banned.

Step 2: Senator 1 (D). There IS an R-ban pending (r_pending = 1 > 0)! D(1) gets banned. active[1] = false, d_count = 1, r_pending = 0. The pending ban was 'used up.'

Step 3: Senator 2 (D). No R-ban pending (r_pending = 0), so D(2) is safe. D creates a pending ban: d_pending = 1.

End of Round 1: r_count = 1, d_count = 1. Both parties alive. d_pending = 1 carries into Round 2.

Round 2:

Step 4: Senator 0 (R). A D-ban IS pending (d_pending = 1 > 0)! R(0) gets banned — this is D(2)'s ban from the end of round 1 wrapping around. active[0] = false, r_count = 0, d_pending = 0.

Step 5: Senator 1: already banned, skip. Senator 2 (D): still active. r_count = 0 → only Dire senators remain.

Result: Return "Dire".

Round-by-Round Simulation with Pending Bans — Watch how senators act in order, creating pending bans that eliminate future opponents. Bans wrap from the end of one round to the start of the next.

Algorithm

  1. Count r_count and d_count from the senate string.
  2. Initialize active[i] = true for all senators. Set r_pending = 0, d_pending = 0.
  3. While both r_count > 0 and d_count > 0:
    a. For each senator i from 0 to n-1:
    • If active[i] is false, skip.
    • If senator is 'R':
      • If d_pending > 0: ban this R (active[i]=false, r_count--, d_pending--).
      • Else: r_pending++ (reserve a ban for the next D).
    • If senator is 'D':
      • If r_pending > 0: ban this D (active[i]=false, d_count--, r_pending--).
      • Else: d_pending++.
  4. Return "Radiant" if r_count > 0, else "Dire".

Code

class Solution {
public:
    string predictPartyVictory(string senate) {
        int n = senate.size();
        vector<bool> active(n, true);
        int rCount = count(senate.begin(), senate.end(), 'R');
        int dCount = n - rCount;
        int rPending = 0, dPending = 0;
        
        while (rCount > 0 && dCount > 0) {
            for (int i = 0; i < n; i++) {
                if (!active[i]) continue;
                if (senate[i] == 'R') {
                    if (dPending > 0) {
                        active[i] = false;
                        rCount--;
                        dPending--;
                    } else {
                        rPending++;
                    }
                } else {
                    if (rPending > 0) {
                        active[i] = false;
                        dCount--;
                        rPending--;
                    } else {
                        dPending++;
                    }
                }
            }
        }
        return rCount > 0 ? "Radiant" : "Dire";
    }
};
class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        active = [True] * n
        r_count = senate.count('R')
        d_count = n - r_count
        r_pending = 0
        d_pending = 0
        
        while r_count > 0 and d_count > 0:
            for i in range(n):
                if not active[i]:
                    continue
                if senate[i] == 'R':
                    if d_pending > 0:
                        active[i] = False
                        r_count -= 1
                        d_pending -= 1
                    else:
                        r_pending += 1
                else:
                    if r_pending > 0:
                        active[i] = False
                        d_count -= 1
                        r_pending -= 1
                    else:
                        d_pending += 1
        
        return "Radiant" if r_count > 0 else "Dire"
class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        boolean[] active = new boolean[n];
        Arrays.fill(active, true);
        int rCount = 0, dCount = 0;
        for (char c : senate.toCharArray()) {
            if (c == 'R') rCount++;
            else dCount++;
        }
        int rPending = 0, dPending = 0;
        
        while (rCount > 0 && dCount > 0) {
            for (int i = 0; i < n; i++) {
                if (!active[i]) continue;
                if (senate.charAt(i) == 'R') {
                    if (dPending > 0) {
                        active[i] = false;
                        rCount--;
                        dPending--;
                    } else {
                        rPending++;
                    }
                } else {
                    if (rPending > 0) {
                        active[i] = false;
                        dCount--;
                        rPending--;
                    } else {
                        dPending++;
                    }
                }
            }
        }
        return rCount > 0 ? "Radiant" : "Dire";
    }
}

Complexity Analysis

Time Complexity: O(n²)

Each round scans all n positions (including banned ones). In the worst case — alternating senators like "RDRDRD..." — each round eliminates exactly one senator from each party. With n/2 senators per party, we need up to n/2 rounds. Each round is O(n), giving O(n × n/2) = O(n²) total.

With n = 10,000, that is up to 50 million operations.

Space Complexity: O(n)

The active boolean array uses O(n) space. All other variables use O(1).

Why This Approach Is Not Efficient

The brute force scans the entire string every round, including senators who were banned in previous rounds. Once a senator is banned, they will never participate again, yet we still check active[i] for them in every future round. This is wasted work.

Consider "RDRDRD..." with 10,000 senators. Round 1 bans 2 senators, but round 2 still scans all 10,000 positions. Round 3 again scans 10,000 positions despite only 9,996 being active. This accumulated waste drives the O(n²) cost.

The key insight: instead of maintaining one big array and scanning past dead entries, we can separate R and D senators into two queues. Each queue only contains live senators. When two senators from opposing parties confront each other, we simply dequeue one from each queue, resolve the confrontation, and re-enqueue the winner. We never waste time scanning past banned senators — they are simply gone from the queue.

This reduces the total work to O(n), since each senator is enqueued and dequeued at most twice.

Optimal Approach - Two-Queue Greedy Simulation

Intuition

Every senator's optimal move is the same: ban the nearest opposing senator who would act next. The nearest threat is always the opponent at the front of their queue.

We separate all senators into two queues based on their party:

  • R-queue holds the positions of all Radiant senators.
  • D-queue holds the positions of all Dire senators.

At each step, we compare the front of both queues — these are the two senators who would act next. Whoever has the smaller position (earlier in the original string) gets to act first. They ban the other senator (removing them from their queue forever). The winner then re-enters their own queue to participate in future rounds.

Here is the clever trick for modeling circular rounds: when a winner re-enters their queue, we add n (the string length) to their position. This ensures:

  1. They are placed after all senators from the current round (since all current positions are 0 to n-1, and position + n ≥ n).
  2. They maintain their relative order among other survivors (if R at position 2 and R at position 5 both survive, they become 2+n and 5+n, preserving the 2-before-5 order).

The process ends when one queue empties — that party has no senators left, and the other party wins.

Step-by-Step Explanation

Let's trace through senate = "RDD". n = 3.

Step 1: Parse the string into two queues:

  • R-queue: [0] (senator at position 0 is R)
  • D-queue: [1, 2] (senators at positions 1 and 2 are D)

Step 2: Confrontation 1. Compare fronts: R(0) vs D(1).

  • Position 0 < Position 1 → R acts first.
  • R(0) bans D(1). Remove D(1) from D-queue.
  • R(0) survives and re-enters as R(0 + 3 = 3).
  • R-queue: [3], D-queue: [2].

Step 3: Confrontation 2. Compare fronts: R(3) vs D(2).

  • Position 2 < Position 3 → D acts first!
  • D(2) bans R(3). Remove R(3) from R-queue.
  • D(2) survives and re-enters as D(2 + 3 = 5).
  • R-queue: [], D-queue: [5].

Step 4: R-queue is empty — no Radiant senators remain. Dire wins!

Key observation in step 3: Even though R(0) won the first confrontation, they returned as R(3). When facing D(2), position 2 < 3, so D acts first. This correctly models the fact that D(2) was 'earlier' in the original string and gets priority in round 2 over the recycled R.

Two-Queue Greedy — R-Queue vs D-Queue Confrontation — Watch two queues face off. The front of each queue confronts the other — smaller position acts first and bans the opponent. The winner re-enters at position + n for the next round.

Algorithm

  1. Create two queues: R_queue and D_queue.
  2. Parse the senate string: for each index i, append i to R_queue if senate[i] == 'R', else to D_queue.
  3. Let n = senate.length.
  4. While both queues are non-empty:
    a. Dequeue front of R_queue → r_pos.
    b. Dequeue front of D_queue → d_pos.
    c. If r_pos < d_pos: R wins. Enqueue r_pos + n back to R_queue.
    d. Else: D wins. Enqueue d_pos + n back to D_queue.
  5. If R_queue is non-empty, return "Radiant". Otherwise return "Dire".

Code

class Solution {
public:
    string predictPartyVictory(string senate) {
        int n = senate.size();
        queue<int> rQ, dQ;
        
        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R') rQ.push(i);
            else dQ.push(i);
        }
        
        while (!rQ.empty() && !dQ.empty()) {
            int rPos = rQ.front(); rQ.pop();
            int dPos = dQ.front(); dQ.pop();
            
            if (rPos < dPos)
                rQ.push(rPos + n);
            else
                dQ.push(dPos + n);
        }
        
        return rQ.empty() ? "Dire" : "Radiant";
    }
};
from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        r_queue = deque()
        d_queue = deque()
        
        for i, ch in enumerate(senate):
            if ch == 'R':
                r_queue.append(i)
            else:
                d_queue.append(i)
        
        while r_queue and d_queue:
            r_pos = r_queue.popleft()
            d_pos = d_queue.popleft()
            
            if r_pos < d_pos:
                r_queue.append(r_pos + n)
            else:
                d_queue.append(d_pos + n)
        
        return "Radiant" if r_queue else "Dire"
class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        Queue<Integer> rQ = new LinkedList<>();
        Queue<Integer> dQ = new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') rQ.offer(i);
            else dQ.offer(i);
        }
        
        while (!rQ.isEmpty() && !dQ.isEmpty()) {
            int rPos = rQ.poll();
            int dPos = dQ.poll();
            
            if (rPos < dPos)
                rQ.offer(rPos + n);
            else
                dQ.offer(dPos + n);
        }
        
        return rQ.isEmpty() ? "Dire" : "Radiant";
    }
}

Complexity Analysis

Time Complexity: O(n)

Each senator is enqueued at most twice — once during initialization and once if they win a confrontation. Each confrontation dequeues exactly one senator from each queue and re-enqueues at most one. Since the total number of senators across both queues starts at n and decreases by 1 per confrontation, there are at most n confrontations. Each is O(1) (deque operations). Total: O(n).

Space Complexity: O(n)

The two queues together hold at most n elements at any time (initially exactly n, and the count decreases by 1 per step). The additional variable storage is O(1).