medium

Dota2 Senate

Decide which party wins by racing two queues of seat numbers and banning the later senator each round.

1. Define the problem

Dota2 Senate

Senators from two parties, Radiant (R) and Dire (D), sit in a fixed order given as a string. They vote in rounds, going left to right and then starting again. On their turn a senator may ban one senator from the other party for good. Return the party that ends up winning. Keep one queue of seat numbers per party . Each round, take the front of each queue: whichever seat number is smaller gets to act first, so that senator bans the other one. The winner then rejoins their own queue with their seat number plus the total number of senators, which puts them in the correct place for the next round. When one queue runs empty, that party has nobody left to act, so the other party wins.

Constraints

  • 1 ≤ senate.length ≤ 104
  • Every character is either R or D
  • Each senator plays as well as possible for their own party
  • The answer is the string Radiant or the string Dire

Example

Inputsenate = 'RDDR'
Output'Radiant'

Explanation The Radiant senator in seat 0 bans the Dire senator in seat 1. The Dire senator in seat 2 then bans the Radiant senator in seat 3. In the next round the seat 0 senator bans the last Dire senator, so Radiant wins.

2. Know the words first

In plain terms

Round
One pass through the seats from left to right. Senators still in the game act in seat order, and banned senators are skipped.
Banned
Removed from the game permanently. A banned senator never acts again and is never counted again.
Seat number plus total
A trick for ordering the next round. Adding the number of senators to a seat number keeps everyone in seat order but places them after everyone still to act this round.
3. Visualize the solution

One row of cells is the seating order; a banned senator becomes a dash

One row of cells is the seating order; a banned senator becomes a dash
Statusinit

Seats hold R, D, D, R. Radiant queue is [0, 3] and Dire queue is [1, 2].

What happens in this step

senate = 'RDDR', total = 4
radiant seats = [0, 3]
dire seats = [1, 2]

Each party has its own queue of seat numbers, kept in seat order.
The front of each queue is that party's next senator to act.
Step 1 of 5

Steps to visualize

  1. Each cell is a seat, holding R, D, or a dash once that senator is banned.
  2. Each round pairs the next R still in the game against the next D still in the game.
  3. The one with the smaller position in the running order acts first and bans the other.
  4. The highlight frame covers the two senators facing each other this round.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the seating order; a banned senator becomes a dash
Statusinit

Seats hold R, D, D, R. Radiant queue is [0, 3] and Dire queue is [1, 2].

What happens in this step

senate = 'RDDR', total = 4
radiant seats = [0, 3]
dire seats = [1, 2]

Each party has its own queue of seat numbers, kept in seat order.
The front of each queue is that party's next senator to act.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function predictPartyVictory(senate) {
  const radiant = [];
  const dire = [];
  const total = senate.length;

  for (let i = 0; i < total; i++) {
    if (senate[i] === 'R') {
      radiant.push(i);
    } else {
      dire.push(i);
    }
  }

  while (radiant.length > 0 && dire.length > 0) {
    const r = radiant.shift();
    const d = dire.shift();

    if (r < d) {
      radiant.push(r + total);
    } else {
      dire.push(d + total);
    }
  }

  return radiant.length > 0 ? 'Radiant' : 'Dire';
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
senate = 'RDDR''Radiant'example from the docstring
senate = 'RD''Radiant'the earlier senator wins a straight one against one
senate = 'RDD''Dire'the larger party wins even though Radiant acts first
senate = 'DDRRR''Dire'a larger case where turn order beats raw numbers
senate = 'R''Radiant'one senator with no opposition, the smallest input
senate = 'D''Dire'the other single senator case

Keep reading