Dota2 Senate

Share

Radiant and Dire senators ban each other. Each senator bans the next opposing senator. Determine winning party.

Example 1
Input: senate="RD" → Output: "Radiant"
Example 2
Input: senate="RDD" → Output: "Dire"

Solution Approach

Greedy with two queues: each senator bans the next available opponent. Re-add winners to back of queue.

  • Create queues of indices for R and D
  • While both queues non-empty: pop front of each
  • Senator with smaller index bans the other
  • Winning senator re-enters queue with index + n
  • Return party of remaining senators
Java
public String predictPartyVictory(String senate) {
    Queue<Integer> R = new LinkedList<>(), D = new LinkedList<>();
    int n = senate.length();
    for (int i = 0; i < n; i++) {
        if (senate.charAt(i) == 'R') R.add(i);
        else D.add(i);
    }
    while (!R.isEmpty() && !D.isEmpty()) {
        int r = R.poll(), d = D.poll();
        if (r < d) R.add(r + n);
        else D.add(d + n);
    }
    return R.isEmpty() ? "Dire" : "Radiant";
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)