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.
1using System;
2using System.Collections.Generic;
3
4public class Dota2Senate {
5 public string PredictPartyVictory(string senate) {
6 Queue<int> radiant = new Queue<int>();
7 Queue<int> dire = new Queue<int>();
8
9 for (int i = 0; i < senate.Length; i++) {
10 if (senate[i] == 'R') radiant.Enqueue(i);
11 else dire.Enqueue(i);
12 }
13
14 int n = senate.Length;
15 while (radiant.Count > 0 && dire.Count > 0) {
16 int rIdx = radiant.Dequeue();
17 int dIdx = dire.Dequeue();
18 if (rIdx < dIdx) radiant.Enqueue(rIdx + n);
19 else dire.Enqueue(dIdx + n);
20 }
21
22 return radiant.Count > 0 ? "Radiant" : "Dire";
23 }
24}
25In C#, queues are realized using the Queue