Problem Explanation

The problem requires us to predict the outcome of a voting mechanism used in a popular game, Dota 2. In this game, there are two parties: Radiant (represented as 'R') and Dire (represented as 'D'). The mechanism of the voting process is divided into step-by-step rounds. At each round, a senator (a player in Dota 2) can do two things:

• Ban the next senator's right to vote.
• If all the senators who are left and still have their rights to vote are from the same party, the senator can declare victory for their party.

The problem is solved by reasoning and applying a queuing system to keep track of senators to perform their actions. By using the features of a queue (FIFO - first in, first out) we can simulate the round-robin nature of the voting process. During each round, a senator can either ban the rights of a senator from the opposing party or declare the victory if all the voting senators are of his party.

Example

Consider a situation where we have senators represented by the string "RDD". The first senator is from the Radiant party. In the first round, he bans the next senator (also from his party). Then the only senator left is from the Dire party and since there are no opposing senators left in the senate, he announces the victory for Dire.

Solution Approach

The solution for this problem involves using two queues, one for each party. We iterate over the string of senators and push their indices to their respective queues.

Then, as long as both queues are not empty, we simulate the voting process. We compare the first senator's index in both queues. If Radiant's index is smaller, it means the Radiant senator can ban Dire's senator first, and we then add the Radiant senator's index back to the queue but add the total number of senators to his index to simulate the next round. This process continues iteratively until one of the queues is empty, being the condition for one party to declare victory.

Python solution

1
2python
3from collections import deque
4
5class Solution:
6    def predictPartyVictory(self, senate: str) -> str:
7        n = len(senate)
8        radiant, dire = deque(), deque()
9
10        # Add everyone to the queue
11        for i, senator in enumerate(senate):
12            if senator == 'R':
13                radiant.append(i)
14            else:
15                dire.append(i)
16
17        while radiant and dire:
18            r, d = radiant.popleft(), dire.popleft()
19            
20            # If radiant senator acts first
21            if r < d:
22                radiant.append(r+n)
23            else:
24                dire.append(d+n)
25
26        return "Radiant" if len(radiant) > len(dire) else "Dire"

Java solution

1
2java
3import java.util.*;
4
5class Solution {
6    public String predictPartyVictory(String senate) {
7        int n = senate.length();
8        Queue<Integer> radiant = new LinkedList<>();
9        Queue<Integer> dire = new LinkedList<>();
10
11        for (int i = 0; i < n; i++) {
12            if (senate.charAt(i) == 'R') {
13                radiant.offer(i);
14            } else {
15                dire.offer(i);
16            }
17        }
18
19        while (!radiant.isEmpty() && !dire.isEmpty()) {
20            int r = radiant.poll();
21            int d = dire.poll();
22            
23            if (r < d) { 
24                radiant.offer(r + n);
25            } else {
26                dire.offer(d + n);
27            }
28        }
29
30        return (radiant.size() > dire.size()) ? "Radiant" : "Dire";
31    }
32}

JavaScript solution

1
2js
3var predictPartyVictory = function(senate) {
4    let n = senate.length;
5    let radiant = [], dire = [];
6
7    for (let i = 0; i < n; ++i) {
8        if (senate[i] === 'R') {
9            radiant.push(i);
10        } else {
11            dire.push(i);
12        }
13    }
14
15    while (radiant.length && dire.length) {
16        if (radiant[0] < dire[0]) {
17            radiant.push(radiant[0] + n);
18        } else {
19            dire.push(dire[0] + n);
20        }
21        radiant.shift();
22        dire.shift();
23    }
24
25    return radiant.length > dire.length ? "Radiant" : "Dire";
26};

C++ solution

1
2cpp
3#include <queue>
4
5using namespace std;
6
7class Solution {
8public:
9    string predictPartyVictory(string senate) {
10        int n = senate.size();
11        queue<int> radiant, dire;
12
13        for (int i = 0; i < n; i++) {
14            if (senate[i] == 'R') {
15                radiant.push(i);
16            } else {
17                dire.push(i);
18            }
19        }
20
21        while (!radiant.empty() && !dire.empty()) {
22            if (radiant.front() < dire.front()) {
23               radiant.push(radiant.front() + n);
24            } else {
25                dire.push(dire.front() + n);
26            }
27            radiant.pop();
28            dire.pop();
29        }
30
31        return (radiant.size() > dire.size()) ? "Radiant" : "Dire";
32    }
33};

C# solution

1
2cs
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7    public string PredictPartyVictory(string senate) {
8        int n = senate.Length;
9        Queue<int> radiant = new Queue<int>();
10        Queue<int> dire = new Queue<int>();
11
12        for (int i = 0; i < n; i++) {
13            if (senate[i] == 'R') {
14                radiant.Enqueue(i);
15            } else {
16                dire.Enqueue(i);
17            }
18        }
19
20        while (radiant.Count != 0 && dire.Count != 0) {
21            if (radiant.Peek() < dire.Peek()) {
22                radiant.Enqueue(radiant.Dequeue() + n);
23            } else {
24                dire.Enqueue(dire.Dequeue() + n);
25            }
26            radiant.Dequeue();
27            dire.Dequeue();
28        }
29
30        return (radiant.Count > dire.Count) ? "Radiant" : "Dire";
31    }
32}

Note that we are adding n to the index and subsequently enqueuing because at each step, the senator gets banned and gets to the end of the queue. Adding n ensures that they maintain their correct position even across multiple rounds of voting.

So, for every round that occurs, the senator with the smaller index gets to ban the senator from the opposing party with the larger index. If Radiant's index is smaller, it means the Radiant senator can ban Dire's senator first, and vice versa.

Both the queues radiant and dire preserve the order of the senators. While a party ("R" or "D") still has their senators remaining in the queue, it means that they still have a chance to win the game. But, as soon as one of the parties' queue becomes empty, it means that they have been completely banned and thus lost the game.

In the end, we simply check which queue is empty and announce the other party as victorious.

The overall time complexity is linear, O(n), where n is the length of the senate string, because at most each senator will cast their vote once. We also have constant, O(1), queue operations such as addition or removal.

The space complexity is also linear, O(n), as we might at most store every senator in the queue.