LeetCode 649. Dota2 Senate

649. Dota2 Senate

 

Problem

---

 

Solution

The key requirements of this problem are as follows:

1. The senate is represesnted as a string consisting of R and D, which represent Radiant and Dire.
2. Each senator can ban one opponent senator in order.
3. The process continues until only one group remains.
4. Return the group that finally left.

To satisfy these requirements, I used queue-based approach without importing any external libraries.

 

First, I separate the senators into two lists, one for Radiant and one for Dire.

 

Using enumerate, I store the index of each senator in the list.

After storing all senators, I initialize idx as 0 and start comparing the senators.

 

While idx is smaller than the length of one of the lists, I compare r[idx] and d[idx].

 

If r[idx] is smaller, this means the Radiant senator acts first and ban the Dire senator.

Therefore, the Radiant senator will appear again in the next round, so I append r[idx] + len(senate) ro the Radiant list.

 

If d[idx] is smaller, the same process is applied to the Dire list.

After each comparison, increase idx by 1.

 

When idx reaches the length of one of the lists, this means that group has no more senators to compare.

 

Therefore, the group with the larger list survives and is returned as the final result.

 

class Solution(object):
    def predictPartyVictory(self, senate):
        r = []
        d = []

        for i, j in enumerate(senate):
            if j == "R":
                r.append(i)
            else:
                d.append(i)

        idx = 0
        while idx < len(r) and idx < len(d):
            if r[idx] < d[idx]:
                r.append(r[idx] + len(senate))
            else:
                d.append(d[idx] + len(senate))
            idx += 1

        return "Radiant" if len(r) > len(d) else "Dire"

 

---

 

https://github.com/K-MarkLee/LeetCode-Practice

GitHub - K-MarkLee/LeetCode-Practice: A collection of LeetCode questions to ace the coding interview! - Created using [LeetHub 2