Dota2 Senate LeetCode solution in Java

1
// Two Queues Solution
2
// Two queues to store the R index and D index.
3
// If the senate can execute his right, the senate is alive and can execute in the next round.
4
// Then we can add the senate back to the queue and process in the next round (idx + N).
5
// Time complexity: O(N), each loop we add/remove 1 senate in the queue.
6
// Space complexity: O(N)
7
class Solution {
8
  public String predictPartyVictory(String senate) {
9
    if (senate == null || senate.length() == 0)
10
      throw new IllegalArgumentException("Invalid input.");
11
    final int N = senate.length();
12
    Queue<Integer> queR = new ArrayDeque<>(); // store the R index
13
    Queue<Integer> queD = new ArrayDeque<>(); // store the D index
14
    for (int i = 0; i < N; i++) {
15
      if (senate.charAt(i) == 'R') {
16
        queR.add(i);
17
      } else {
18
        queD.add(i);
19
      }
20
    }
21
    while (!queR.isEmpty() && !queD.isEmpty()) {
22
      int r = queR.poll();
23
      int d = queD.poll();
24
      if (r < d) { // R is alive in the next round.
25
        queR.add(r + N);
26
      } else { // D is alive in the next round.
27
        queD.add(d + N);
28
      }
29
    }
30
    return queR.isEmpty() ? "Dire" : "Radiant";
31
  }
32
}