LeetCode 649: Dota2 Senate Solution

Master LeetCode problem 649 (Dota2 Senate), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

649. Dota2 Senate

Medium

String Greedy Queue

Problem Explanation

Explanation

To solve this problem, we can simulate the voting process by using a queue to represent the order of senators. We iterate through the queue, and for each senator, we check if they can ban a senator from the opposing party. If they cannot ban anyone, they are skipped. If they can ban a senator, we remove the banned senator from the queue. We continue this process until either all senators from one party are banned or only one party remains in the queue.

Algorithm:

Create a queue to represent the order of senators.
Iterate through the queue until one party wins or all senators have voted.
For each senator:
- If they can ban a senator from the opposing party, ban that senator and continue to the next senator.
- If they cannot ban anyone, remove them from the queue.
Repeat steps 2-3 until only one party remains in the queue or all senators have voted.

Time Complexity:

The time complexity of this approach is O(n), where n is the number of senators.

Space Complexity:

The space complexity is O(n) for the queue.

Solution Code

class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Integer> radiant = new LinkedList<>();
        Queue<Integer> dire = new LinkedList<>();

        for (int i = 0; i < senate.length(); i++) {
            char party = senate.charAt(i);
            if (party == 'R') {
                radiant.offer(i);
            } else {
                dire.offer(i);
            }
        }

        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int rIndex = radiant.poll();
            int dIndex = dire.poll();

            if (rIndex < dIndex) {
                radiant.offer(rIndex + senate.length());
            } else {
                dire.offer(dIndex + senate.length());
            }
        }

        return radiant.isEmpty() ? "Dire" : "Radiant";
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 649 (Dota2 Senate)?

This page provides optimized solutions for LeetCode problem 649 (Dota2 Senate) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 649 (Dota2 Senate)?

The time complexity for LeetCode 649 (Dota2 Senate) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 649 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 649 in Java, C++, or Python.

Back to LeetCode Solutions