Dota2 Senate — LeetCode 649 Python Solution

The problem

In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties.

Example

Input

senate = "RD"

Output

"Radiant"

Explanation

The first senator comes from Radiant and he can just ban the next senator's right in round 1.

Python solution

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        qr = deque()
        qd = deque()
        for i, c in enumerate(senate):
            if c == "R":
                qr.append(i)
            else:
                qd.append(i)
        n = len(senate)
        while qr and qd:
            if qr[0] < qd[0]:
                qr.append(qr[0] + n)
            else:
                qd.append(qd[0] + n)
            qr.popleft()
            qd.popleft()
        return "Radiant" if qr else "Dire"

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 649. Dota2 Senate is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems