⚡Flashcard Drill➔
NeetCode #791LC-649MediumGreedyNC 250
← Back to All Problems

#791 · #649 · Dota2 Senate(Dota2 参议院)

📌 Problem Statement & Constraints

In the Dota2 senate, each senator is from the Radiant or Dire party. In each round, senators act in order; each may ban one opposing senator (who then loses all future rights). A senator with no rights is skipped. Return the winning party. Constraints: 1 <= senate.length <= 10^4, senate[i] is R or D.

💡 Core Algorithmic Approaches

  1. Put the indices of R and D senators into two queues.
  2. In each step compare the front indices: the senator with the smaller index acts first and bans the other, whose index is popped.
  3. The surviving senator is re-appended with index i + n to represent the next round.
  4. Repeat until one queue is empty; that party wins.

💻 Benchmark Python3 Implementation

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        from collections import deque
        n = len(senate)
        r = deque(i for i, c in enumerate(senate) if c == "R")
        d = deque(i for i, c in enumerate(senate) if c == "D")
        while r and d:
            if r[0] < d[0]:
                d.popleft()            # R bans the earliest D
                r.append(r.popleft() + n)
            else:
                r.popleft()
                d.append(d.popleft() + n)
        return "Radiant" if r else "Dire"

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each senator is processed a bounded number of times.
💾 Space Complexity
O(n): the two queues.

⚠️ Interview Pitfalls & Follow-ups

  • Simulating round by round with a list: the repeated passes make it O(n^2) in the worst case.
  • Assuming a banned senator can still ban: a senator who is banned loses the right to act, which the queue pop enforces.
  • Forgetting the + n offset: without it the round ordering is lost and the wrong party can win.
  • Returning the party with the larger initial count: the interleaving of indices decides the winner, not the raw counts.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems