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
- Put the indices of
RandDsenators into two queues. - In each step compare the front indices: the senator with the smaller index acts first and bans the other, whose index is popped.
- The surviving senator is re-appended with index
i + nto represent the next round. - 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
+ noffset: 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.