algoadvance

Leetcode 649. Dota2 Senate

Problem Statement

The Dota2 match consists of two parties: the Radiant and the Dire. The Dota2 senate consists of senators from both parties who vote on a proposed change to the game. Given a string senate representing each senator in the senate where:

The voting process follows these rules:

  1. Each senator can ban one opposing senator’s right to vote.
  2. If a senator has been banned, they cannot participate in the voting process.
  3. The votes are counted in rounds. In each round, each senator will choose one senator to ban according to the order given in the input string.
  4. The process continues until only senators from one party remain.

Your task is to determine which party will remain after the voting process ends. Return the string “Radiant” if the Radiant party wins and “Dire” if the Dire party wins.

Clarifying Questions

  1. Can the input string be empty?
    • No, there will always be at least one senator from either party.
  2. What is the maximum length of the input string?
    • The length can go up to 10^4.
  3. Can we assume that the input is valid and contains only ‘R’ and ‘D’ characters?
    • Yes, the input will always be valid.

Strategy

  1. Use two queues to manage the indices of the Radiant (‘R’) and Dire (‘D’) senators.
  2. Process the senate in rounds:
    • In each round, compare the front senators of the two queues.
    • The senator appearing earlier in the list (smaller index) will ban the other.
    • Move the winning senator to the end of its queue to represent it being able to vote in the next round.
    • Discard the losing senator by dequeuing it.
  3. Repeat the process until one of the queues is empty.
  4. The remaining non-empty queue determines the winning party.

Code

import java.util.LinkedList;
import java.util.Queue;

public class Dota2Senate {
    public String predictPartyVictory(String senate) {
        Queue<Integer> radiant = new LinkedList<>();
        Queue<Integer> dire = new LinkedList<>();
        
        // Populate the queues with the indices of each senator
        for (int i = 0; i < senate.length(); i++) {
            if (senate.charAt(i) == 'R') {
                radiant.add(i);
            } else {
                dire.add(i);
            }
        }
        
        // Process the voting rounds
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int rIndex = radiant.poll();
            int dIndex = dire.poll();
            
            // Lower index senator bans the other
            if (rIndex < dIndex) {
                radiant.add(rIndex + senate.length());
            } else {
                dire.add(dIndex + senate.length());
            }
        }
        
        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

Time Complexity

Thus, the total time complexity is O(n), which is efficient for the input size constraint of 10^4.

Final Note

This approach ensures each round is efficiently handled, and queues provide an intuitive and straightforward way to handle the cyclic nature of voting rounds in this problem.

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