Problem of The Day: Dota2 Senate

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    public string PredictPartyVictory(string senate) {
        Queue<char> queue = new Queue<char>();
        foreach (var c in senate) {
            queue.Enqueue(c);
        }
        while (queue.Count > 0) {
            var curr = queue.Dequeue();
            var banned = curr == 'R' ? 'D' : 'R';
            var n = queue.Count;
            var nextQueue = new Queue<char>();
            var isRemoved = false;
            for (int i = 0; i < n; i ++) {
                var c = queue.Dequeue();
                if (!isRemoved && c == banned) {
                    isRemoved = true;
                    continue;
                }
                nextQueue.Enqueue(c);
            }
            nextQueue.Enqueue(curr);
            queue = nextQueue;
            if (!isRemoved) {
                break;
            }
        }

        var r = 0;
        var d = 0;
        foreach (var c in queue) {
            if (c == 'R') {
                r++;
            } else {
                d++;
            }
        }

        return r > d ? "Radiant" : "Dire";
    }
}

Improve Code

public class Solution {
    public string PredictPartyVictory(string senate) {
        int n = senate.Length;
        Queue<int> radiant = new();
        Queue<int> dire = new();

        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R')
                radiant.Enqueue(i);
            else
                dire.Enqueue(i);
        }

        while (radiant.Count > 0 && dire.Count > 0) {
            int r = radiant.Dequeue();
            int d = dire.Dequeue();

            if (r < d)
                radiant.Enqueue(r + n);
            else
                dire.Enqueue(d + n);
        }

        return radiant.Count > 0 ? "Radiant" : "Dire";
    }
}

Editorial

Apprach 1: Greedy

public class Solution {
    public string PredictPartyVictory(string senate) {

        // Count of Each Type of Senator to check for Winner
        int rCount = senate.Count(c => c == 'R');
        int dCount = senate.Length - rCount;

        // Ban the candidate "toBan", immediate next to "startAt"
        // If have to loop around, then it means next turn will be of
        // senator at same index. Returns loop around boolean
        bool ban(char toBan, int startAt) {
            bool loopAround = false;
            int pointer = startAt;

            while (true) {
                if (pointer == 0) {
                    loopAround = true;
                }
                if (senate[pointer] == toBan) {
                    senate = senate.Remove(pointer, 1);
                    break;
                }
                pointer = (pointer + 1) % senate.Length;
            }

            return loopAround;
        }

        // Turn of Senator at this index
        int turn = 0;

        // While No Winner
        while (rCount > 0 && dCount > 0) {

            // Ban the next opponent, starting at one index ahead
            // Taking MOD to loop around.
            // If index of banned senator is before current index,
            // then we need to decrement turn by 1, as we have removed
            // a senator from list
            if (senate[turn] == 'R') {
                bool bannedSenatorBefore = ban('D', (turn + 1) % senate.Length);
                dCount--;
                if (bannedSenatorBefore) {
                    turn--;
                }
            } else {
                bool bannedSenatorBefore = ban('R', (turn + 1) % senate.Length);
                rCount--;
                if (bannedSenatorBefore) {
                    turn--;
                }
            }

            // Increment turn by 1
            turn = (turn + 1) % senate.Length;
        }

        // Return Winner depending on count
        return dCount == 0 ? "Radiant" : "Dire";
    }
}

Approach 2: Boolean Array

public class Solution {
    public string PredictPartyVictory(string senate) {

        // Count of Each Type of Senator to check for Winner
        int rCount = senate.Count(x => x == 'R');
        int dCount = senate.Length - rCount;

        // To mark Banned Senators
        bool[] banned = new bool[senate.Length];

        // Ban the candidate "toBan", immediate next to "startAt"
        Action<char, int> ban = (toBan, startAt) => {
            // Find the next eligible senator of "toBan" type
            // On found, mark him as banned
            while (true) {
                if (senate[startAt] == toBan && !banned[startAt]) {
                    banned[startAt] = true;
                    break;
                }
                startAt = (startAt + 1) % senate.Length;
            }
        };

        // Turn of Senator at this Index
        int turn = 0;

        // While both parties have at least one senator
        while (rCount > 0 && dCount > 0) {

            if (!banned[turn]) {
                if (senate[turn] == 'R') {
                    ban('D', (turn + 1) % senate.Length);
                    dCount--;
                } else {
                    ban('R', (turn + 1) % senate.Length);
                    rCount--;
                }
            }

            turn = (turn + 1) % senate.Length;
        }

        // Return Winner
        return dCount == 0 ? "Radiant" : "Dire";
    }
}

Approach 4: Two Queues

public class Solution {
    public string PredictPartyVictory(string senate) {

        // Number of Senator
        int n = senate.Length;

        // Queues with Senator's Index.
        // Index will be used to find the next turn of Senator
        Queue<int> rQueue = new Queue<int>();
        Queue<int> dQueue = new Queue<int>();

        // Populate the Queues
        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R') {
                rQueue.Enqueue(i);
            } else {
                dQueue.Enqueue(i);
            }
        }

        // While both parties have at least one Senator
        while (rQueue.Count > 0 && dQueue.Count > 0) {

            // Pop the Next-Turn Senate from both Q.
            int rTurn = rQueue.Dequeue();
            int dTurn = dQueue.Dequeue();

            // ONE having a larger index will be banned by a lower index
            // Lower index will again get Turn, so EN-Queue again
            // But ensure its turn comes in the next round only
            if (dTurn < rTurn) {
                dQueue.Enqueue(dTurn + n);
            } else {
                rQueue.Enqueue(rTurn + n);
            }
        }

        // One's which Empty is not winner
        return rQueue.Count == 0 ? "Dire" : "Radiant";
    }
}

Approach 5: Single Queue

public class Solution {
    public string PredictPartyVictory(string senate) {

        // Number of Senators of each party
        int rCount = 0, dCount = 0;

        // Floating Ban Count
        int dFloatingBan = 0, rFloatingBan = 0;

        // Queue of Senators
        Queue<char> q = new Queue<char>();
        foreach (char c in senate) {
            q.Enqueue(c);
            if (c == 'R') rCount++;
            else dCount++;
        }

        // While any party has eligible Senators
        while (rCount > 0 && dCount > 0) {

            // Pop the senator with turn
            char curr = q.Dequeue();

            // If eligible, float the ban on the other party, enqueue again.
            // If not, decrement the floating ban and count of the party.
            if (curr == 'D') {
                if (dFloatingBan > 0) {
                    dFloatingBan--;
                    dCount--;
                } else {
                    rFloatingBan++;
                    q.Enqueue('D');
                }
            } else {
                if (rFloatingBan > 0) {
                    rFloatingBan--;
                    rCount--;
                } else {
                    dFloatingBan++;
                    q.Enqueue('R');
                }
            }
        }

        // Return the party with eligible Senators
        return rCount > 0 ? "Radiant" : "Dire";
    }
}