Problem statement

https://leetcode.com/problems/dota2-senate/

Solution

The main idea of solution is that it is always best choice is to ban the closest person after you from the opposite party. The best way to implement this process is to use queue or even two queues: first one for one party and second for another. Each moment of time we check whose turn is now and we add this candidate to the end with number increased by n to the end of our queue.

Complexity

Time complexity will be O(n), because each step we remove two elements and add only one; space is O(n) as well.

Code

class Solution:
    def predictPartyVictory(self, senate):
        n = len(senate)
        R, D = deque(), deque()
        for i in range(n):
            if senate[i] == "D": D.append(i)
            else: R.append(i)

        while D and R:
            if D[0] > R[0]:
                R.append(R[0] + n)
            else: 
                D.append(D[0] + n)

            D.popleft()
            R.popleft()

        return "Dire" if D else "Radiant"