algoadvance

Leetcode 649. Dota2 Senate

Problem Statement

The Dota2 senate consists of senators representing two parties: the Radiant and the Dire. The senators sit in a row and each senator can either ban one senator of the opposite party or announce victory if all the others are banned.

Given a string senate consisting of characters ‘R’ and ‘D’ representing Radiant and Dire senators respectively, write a solution to predict which party will announce the victory. The output should be either ‘Radiant’ or ‘Dire’.

Clarifying Questions

  1. What is the size limit of the senate string?
    • The size of the string can be up to 10,000.
  2. Should we assume that each senator uses their banning right optimally?
    • Yes, each senator will use their banning right as soon as possible in an optimal manner.
  3. Can there be ties in the decision process?
    • No, there will always be a clear winner as per the problem statement.

Strategy

  1. Using Queues: We will use two queues to manage the indexes of the senators from each party. This helps us simulate the rounds in which we can effectively determine who gets to ban whom.
  2. Simulation of Banning:
    • Each round, the senator with the smaller index in the queue gets to ban a senator from the opposite party.
    • The banned senator’s index is removed from the queue.
    • The banning senator’s index is moved to the end of the queue representing that they will come back in the next round.

This ensures that we simulate the banning process correctly as per their positions in the senate string.

Code

#include <iostream>
#include <queue>
#include <string>

std::string predictPartyVictory(std::string senate) {
    std::queue<int> radiant, dire;
    int n = senate.size();

    // Populate the queues with the initial positions of 'R' and 'D'
    for (int i = 0; i < n; ++i) {
        if (senate[i] == 'R') {
            radiant.push(i);
        } else { // senate[i] == 'D'
            dire.push(i);
        }
    }

    // Process banning in rounds
    while (!radiant.empty() && !dire.empty()) {
        int rIndex = radiant.front();
        int dIndex = dire.front();
        radiant.pop();
        dire.pop();

        // The one with the smaller index bans the other
        if (rIndex < dIndex) {
            radiant.push(rIndex + n); // Radiant bans Dire and returns in next round
        } else {
            dire.push(dIndex + n); // Dire bans Radiant and returns in next round
        }
    }

    // Determine the winner
    return radiant.empty() ? "Dire" : "Radiant";
}

int main() {
    std::string senate = "RDD";
    std::cout << predictPartyVictory(senate) << std::endl; // Output should be "Dire"
    return 0;
}

Time Complexity

Hence, the overall time complexity is O(n), where n is the length of the senate string. This is efficient and should handle the upper constraint of 10,000 efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI