Dota2 Senate

NeetCode: Dota2 Senate · LeetCode: 649. Dota2 Senate · Difficulty: Medium

The senate is a string of 'R' (Radiant) and 'D' (Dire). In each round, going in order, every senator that has not been banned may ban one senator of the other party (who then loses all rights) or, if all remaining senators are from one party, announce victory for that party. The process repeats around the circle until a party wins. Assuming both parties play optimally, return "Radiant" or "Dire".

Example

Text

Input:  senate = "RD"     Output: Radiant
Input:  senate = "RDD"    Output: Dire

Brute force: simulate the circle

The greedy choice is to ban the opponent who would act soonest. Banning an opponent who acts later leaves the earlier one free to ban a teammate first.

Simulate directly with a banned flag per senator, sweeping the circle repeatedly. An active senator bans the first non-banned opponent after them, wrapping around; if there is none, their party wins. Each ban may scan O(n) senators and there can be O(n) bans, so the simulation is quadratic.

Java

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        boolean[] banned = new boolean[n];
        while (true) {
            for (int i = 0; i < n; i++) {
                if (banned[i]) {
                    continue;
                }
                int target = -1;
                for (int d = 1; d < n; d++) {
                    int j = (i + d) % n;
                    if (!banned[j] && senate.charAt(j) != senate.charAt(i)) {
                        target = j;
                        break;
                    }
                }
                if (target == -1) {
                    return senate.charAt(i) == 'R' ? "Radiant" : "Dire";
                }
                banned[target] = true;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.predictPartyVictory("RD"));
        System.out.println(s.predictPartyVictory("RDD"));
        System.out.println(s.predictPartyVictory("DDRRR"));
        System.out.println(s.predictPartyVictory("D"));
    }
}

Output

Radiant
Dire
Dire
Dire

senate.charAt(j) != senate.charAt(i) compares two char values, which is a numeric comparison and is correct for primitives. Time: O(n^2). Space: O(n).

Optimal: two queues of indices

Store the positions of the R senators in one queue and the D senators in another. Compare the two front indices: the smaller index acts first, so that senator bans the other. The surviving senator is re-enqueued with index + n, its position in the next round. Repeat until one queue is empty. Every step removes one senator, so there are fewer than n steps of O(1) work each.

ArrayDeque<Integer> is Java's queue: add appends at the back and poll removes from the front.

Java

import java.util.ArrayDeque;

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        ArrayDeque<Integer> radiant = new ArrayDeque<>();
        ArrayDeque<Integer> dire = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') {
                radiant.add(i);
            } else {
                dire.add(i);
            }
        }
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int r = radiant.poll();
            int d = dire.poll();
            if (r < d) {
                radiant.add(r + n);
            } else {
                dire.add(d + n);
            }
        }
        return dire.isEmpty() ? "Radiant" : "Dire";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.predictPartyVictory("RD"));
        System.out.println(s.predictPartyVictory("RDD"));
        System.out.println(s.predictPartyVictory("DDRRR"));
        System.out.println(s.predictPartyVictory("D"));
    }
}

Output

Radiant
Dire
Dire
Dire

Time: O(n). Space: O(n).