Facebook Pixel

649. Dota2 Senate

MediumGreedyQueueString
Leetcode Link

Problem Description

In the given problem, we are simulating a political power struggle within a senate of a fantasy world known as Dota2. The senate is made up of two parties, Radiant and Dire. Each senator, in turn, has the opportunity to exercise one of two rights—either banning another senator, effectively removing them from the game, or declaring victory for their party if all remaining senators are from their own party.

The outcome we seek to predict is which party will ultimately succeed in passing a change in the Dota2 game by eliminating the opposition's ability to vote. The senators are presented in a string where each character represents a senator from either the Radiant (as 'R') or the Dire (as 'D'). Senators act in the order they appear in the string, and once a senator is banned, they are skipped in subsequent rounds of the process.

Since each senator is smart and employs the best strategy for their party, we need to simulate the rounds of banning to determine which party wins.

Intuition

The intuition behind the solution involves simulating the process using a queue data structure. For simplicity and efficiency, we use a separate queue for each party, recording the positions (indices) of their senators in the senate list. Our goal is to simulate each round where senators ban their immediate opponent senator (if available).

The key insights to arrive at the solution are:

  1. Senators will always ban the next senator of the opposite party to maximize their party's chance of victory.
  2. Once a senator has made a move, they go to the end of the queue but with an increased index representing their new position in the "virtual" order. This is done to maintain the cyclic nature of the senate arrangement.
  3. The process continues until one party's queue is empty, meaning no more senators from that party are left to cast votes or make bans.

By dequeuing the first senator of each party and having them ban the opponent's first senator, we simulate the banning process while keeping track of the new positions. If a Radiant senator acts before a Dire senator, they add to the end of their queue by considering the size of the senate (senate), effectively banning the first Dire senator. The same logic applies when a Dire senator acts before a Radiant senator.

The simulation continues until one party has no remaining senators, at which point the surviving party is declared the winner. This approach ensures that we correctly identify which party would win in an ideal scenario where each senator acts optimally for their party's interest.

Learn more about Greedy and Queue patterns.

Solution Approach

The solution uses a greedy algorithm to simulate the senate's round-based decision-making process. A greedy algorithm makes the locally optimal choice at each stage with the hope of finding a global optimum. In this context, the local optimum is for each senator to ban an opposing party senator as early as possible.

We utilize two queues represented by the deque data structure from Python's collections module:

  • qr queue stores the indices of the Radiant senators.
  • qd queue stores the indices of the Dire senators.

The indices allow us to keep track of the order of the senators and their relative positions in the simulated rounds.

Here's the approach step by step, in alignment with the code provided:

  1. Iterate through the senate string and fill the queues qr and qd with indices of the senators belonging to the Radiant and Dire parties, respectively.

  2. Enter a loop that will run until one of the queues is empty. The condition while qr and qd: ensures that the loop continues as long as there are senators from both parties available to take action.

  3. In each iteration of the loop:

    • Compare the indices at the front of both qr and qd which represents the order in which the senators will take action. The senator with the lower index is able to act first.
    • If the first Radiant senator (qr[0]) is before the first Dire senator (qd[0]), the Radiant senator will ban the Dire senator. The Radiant senator's index is then added back to the qr queue, incremented by n, which is the length of the senate string. This effectively places them at the end of the order for the next round.
    • Similarly, if the Dire senator acts first, they will ban the Radiant senator, and their index (incremented by n) will be added back to the qd queue.
    • After a senator has acted (either banning or being banned), we remove them from the front of the queue using popleft().

  4. After exiting the loop, we check which queue still has senators left, which determines the victorious party. If qr is not empty, Radiant wins; otherwise, Dire wins.

  5. Finally, return "Radiant" if the qr queue has senators left, or "Dire" if the qd queue has senators left.

This approach ensures that each senator acts in the best interest of their party by banning the first available opposition senator and then waiting for their next turn at the end of the senate order.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example with the senate string RDD. We'll simulate the process to see which party comes out victorious.

  1. We initialize two queues: qr for Radiant and qd for Dire. Given the senate string RDD, qr will initially contain [0] because the first senator (index 0) is from the Radiant party, and qd will contain [1, 2] because the second and third senators (indices 1 and 2) are from the Dire party.

  2. Now, we enter the main loop where we process each senator's actions:

    • Both qr and qd are not empty, so we continue.
    • We compare the front of both queues: qr[0] is 0, and qd[0] is 1. Since the Radiant senator (R) at index 0 is the first in line, they act by banning the first Dire senator (D) at index 1.
    • We remove the banned Dire senator from queue qd by dequeuing it, and then we add the Radiant senator's index incremented by n (the length of the senate string) to represent their new virtual position at the end of the next round. Since n is 3 here, we add 0 + 3 to qr, which becomes [3].
    • The qd queue now looks like [2], as the first Dire senator was banned.

  3. Continuing with the main loop:

    • Comparing the indices again, we see qr[0] is 3 (which is virtually 0 in the next round), and qd[0] is 2. The Dire senator at index 2 acts next, since they are the only one left and thus have the lowest current index.
    • The Dire senator bans the first Radiant senator positioned at virtual index 3 (original index 0 returned to the queue). Since nobody is left in the Radiant queue now, qd is decremented by dequeuing the acting senator, and their new indexed position 2 + 3 = 5 is added back to the qd queue.

  4. We check the queues after the loop iteration:

    • The qr queue is empty, which indicates that there are no more Radiant senators to take action.
    • The qd queue has one senator left at index 5 (virtually 2).

  5. Since qr is empty and qd still has a senator, the victorious party is Dire.

In this example, the final output is "Dire", and the process demonstrates the greedy approach of banning the opponent's next available senator to ensure the best outcome for one's own party.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def predict_party_victory(self, senate: str) -> str:
5        # Initialize queues for Radiant and Dire senators' indices
6        queue_radiant = deque()
7        queue_dire = deque()
8      
9        # Populate initial queues with the indices of the Radiant and Dire senators
10        for index, senator in enumerate(senate):
11            if senator == "R":
12                queue_radiant.append(index)
13            else:
14                queue_dire.append(index)
15      
16        # Calculate the length of the senate for future indexing
17        n = len(senate)
18      
19        # Process the two queues
20        while queue_radiant and queue_dire:
21            # Take the first senator from each queue and compare their indices
22            if queue_radiant[0] < queue_dire[0]:
23                # If the Radiant senator comes first, they ban a Dire senator
24                # and put themselves at the back of their queue with a new hypothetical index
25                queue_radiant.append(queue_radiant[0] + n)
26            else:
27                # If the Dire senator comes first, they ban a Radiant senator
28                # and put themselves at the back of their queue with a new hypothetical index
29                queue_dire.append(queue_dire[0] + n)
30          
31            # Remove the senators who have exercised their powers
32            queue_radiant.popleft()
33            queue_dire.popleft()
34      
35        # Return the winning party's name based on which queue still has senators
36        return "Radiant" if queue_radiant else "Dire"
37
1class Solution {
2    public String predictPartyVictory(String senate) {
3        int totalSenators = senate.length();
4        Deque<Integer> radiantQueue = new ArrayDeque<>();
5        Deque<Integer> direQueue = new ArrayDeque<>();
6
7        // Populate queues with the indices of 'R' and 'D' senators
8        for (int i = 0; i < totalSenators; ++i) {
9            if (senate.charAt(i) == 'R') {
10                radiantQueue.offer(i);
11            } else {
12                direQueue.offer(i);
13            }
14        }
15      
16        // Process the queues until one of them is empty
17        while (!radiantQueue.isEmpty() && !direQueue.isEmpty()) {
18            int radiantIndex = radiantQueue.peek();
19            int direIndex = direQueue.peek();
20          
21            // The senator with the lower index bans the opposing senator
22            if (radiantIndex < direIndex) {
23                // The radiant senator bans a dire senator and gets back in line
24                radiantQueue.offer(radiantIndex + totalSenators);
25            } else {
26                // The dire senator bans a radiant senator and gets back in line
27                direQueue.offer(direIndex + totalSenators);
28            }
29
30            // Remove the senators that have already made a ban
31            radiantQueue.poll();
32            direQueue.poll();
33        }
34
35        // Declare the winner depending on which queue is not empty
36        return radiantQueue.isEmpty() ? "Dire" : "Radiant";
37    }
38}
39
1class Solution {
2public:
3    // Function to predict the winner of the senate dispute.
4    string predictPartyVictory(string senate) {
5        int n = senate.size(); // Get the size of the senate string
6      
7        // Queues to store the indices of 'R' and 'D' senators
8        queue<int> radiantQueue;
9        queue<int> direQueue;
10      
11        // Populate the initial queues with the indices of each senator
12        for (int i = 0; i < n; ++i) {
13            if (senate[i] == 'R') {
14                radiantQueue.push(i);
15            } else {
16                direQueue.push(i);
17            }
18        }
19      
20        // Loop as long as both queues have senators remaining
21        while (!radiantQueue.empty() && !direQueue.empty()) {
22            int radiantIndex = radiantQueue.front(); // Get the index of the front radiant senator
23            int direIndex = direQueue.front(); // Get the index of the front dire senator
24          
25            radiantQueue.pop(); // Remove the front radiant senator from the queue
26            direQueue.pop(); // Remove the front dire senator from the queue
27          
28            // The senator with the smaller index bans the other from the next round
29            if (radiantIndex < direIndex) {
30                // Radiant senator wins this round and re-enters queue with index increased by n
31                radiantQueue.push(radiantIndex + n);
32            } else {
33                // Dire senator wins this round and re-enters queue with index increased by n
34                direQueue.push(direIndex + n);
35            }
36        }
37      
38        // If the radiant queue is empty, Dire wins; otherwise, Radiant wins
39        return radiantQueue.empty() ? "Dire" : "Radiant";
40    }
41};
42
1function predictPartyVictory(senate: string): string {
2    // Determine the length of the senate string
3    const senateLength = senate.length;
4    // Initialize queues to keep track of the indexes of 'R' (Radiant) and 'D' (Dire) senators
5    const radiantQueue: number[] = [];
6    const direQueue: number[] = [];
7
8    // Populate the queues with the initial positions of the senators
9    for (let i = 0; i < senateLength; ++i) {
10        if (senate[i] === 'R') {
11            radiantQueue.push(i);
12        } else {
13            direQueue.push(i);
14        }
15    }
16
17    // Run the simulation until one party has no senators left
18    while (radiantQueue.length > 0 && direQueue.length > 0) {
19        // Remove the first senator in each queue to simulate a round
20        const radiantSenatorIndex = radiantQueue.shift()!;
21        const direSenatorIndex = direQueue.shift()!;
22
23        // The senator with the lower index bans the opponent senator from the current round
24        // Then, the winning senator gets re-added to the queue for the next round
25        if (radiantSenatorIndex < direSenatorIndex) {
26            radiantQueue.push(radiantSenatorIndex + senateLength);
27        } else {
28            direQueue.push(direSenatorIndex + senateLength);
29        }
30    }
31
32    // After one party has no senators left, return the name of the winning party
33    return radiantQueue.length > 0 ? 'Radiant' : 'Dire';
34}
35

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the length of the senate string.

Reasoning:

  • We loop through each character of the string to build the initial qr and qd queues - this is an O(N) operation.
  • In the while loop, in each iteration, one senator from each party (R and D) gets 'compared', and one is turned 'inactive' for the current round. Each senator will be dequeued and potentially re-queued once per round. The number of rounds is proportional to the number of senators, because in each round at least one senator is banned from further participation until all senators from the opposing party have been banned.
  • Since qr.append(qr[0] + n) and qd.append(qd[0] + n) just change the index for the next round, the O(N) operations within the loop are repeated N times in the worst case (every senator goes once per round). However, due to the nature of the problem, the loop will terminate when one party has no more active senators, so it does not strictly go N rounds.

Space Complexity

The space complexity of the code is O(N), where N is the length of the senate string.

Reasoning:

  • Two queues, qr for Radiant senators and qd for Dire senators, each can hold at most N elements if all the senators are from one party.
  • No other data structures are used that grow with the input size - thus, the dominant term is the space used by the two queues.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Greedy Introduction

Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More