Sponsored
Sponsored
We utilize two separate queues to maintain indices of Radiant and Dire senators. In each round, senators from both parties execute their rights and effect bans on their opponent. The process continues until one queue becomes empty, indicating that all senators from one party have been eliminated.
Time Complexity: O(n), where n is the length of the senate, since each senator is processed a finite number of times.
Space Complexity: O(n), for storing indices in queues.
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class Dota2Senate {
5 public String predictPartyVictory(String senate) {
6 Queue<Integer> radiant = new LinkedList<>();
7 Queue<Integer> dire = new LinkedList<>();
8 int n = senate.length();
9
10 for (int i = 0; i < n; i++) {
11 if (senate.charAt(i) == 'R') radiant.add(i);
12 else dire.add(i);
13 }
14
15 while (!radiant.isEmpty() && !dire.isEmpty()) {
16 int rIdx = radiant.poll();
17 int dIdx = dire.poll();
18 if (rIdx < dIdx) radiant.add(rIdx + n);
19 else dire.add(dIdx + n);
20 }
21
22 return radiant.isEmpty() ? "Dire" : "Radiant";
23 }
24}
25Using Java's LinkedList class, which implements the Queue interface, this solution works by enqueuing the indices of Radiant and Dire senators, processing their ability to ban opposing votes, and continually looping until one of the queues is empty, similar to the C++ solution.