Dota2 Senate LeetCode 649 Guide

LeetCode 649 Dota2 Senate presents a string of characters, each either R (Radiant) or D (Dire), representing senators in a circular voting session. In each round, every senator can either ban one senator from the opposing party or, if no opposition remains, declare victory for their own party. The goal is to determine which party — "Radiant" or "Dire" — ultimately wins.

The process is circular: senators act in the order they appear in the string, and the round repeats until one side is completely eliminated. A senator who has been banned cannot act. The string length n can be up to 10,000, so an efficient simulation is required — a naive O(n^2) per-round approach would be too slow.

Understanding the circular nature is key. After all senators in the original string have acted once, any surviving senators begin again in the same relative order. This circularity is what drives the two-queue design: instead of modifying a circular list, we simulate re-entry by appending the winning senator back to their queue with an updated index.

The optimal strategy for every senator is to ban the earliest remaining opponent — the one who would act next in the queue. Banning any other senator is strictly suboptimal: if you skip the next opponent, they will act before your banned senator would have, costing your party an ally. The greedy choice is always to eliminate the most immediate threat.

This greedy approach is provably correct by an exchange argument. Suppose senator A at position i chooses to ban senator C at position k instead of the nearer opponent B at position j (where j < k). Then B acts before C would have, banning one of A's allies. The net result is no better than if A had banned B directly. Therefore, banning the earliest opponent is always at least as good as any other choice.

The greedy insight reduces the problem to a simple comparison: at each step, compare the front of the Radiant queue and the front of the Dire queue. Whichever senator has the smaller index acts first and eliminates the other. The winner re-enters their queue at index+n to represent participation in the next round.

Initialize two queues: one for Radiant senator indices and one for Dire senator indices, populated by scanning the input string left to right. For example, "RDD" gives radiant=[0] and dire=[1,2]. These indices represent the order in which senators act in the first round.

While both queues are non-empty, compare the front elements. The senator with the smaller index acts first and bans the senator at the front of the opposing queue. The winner is then re-inserted into their own queue at index+n, placing them at the end of the circular order. The loser is discarded — popped from their queue and not re-inserted.

Repeat until one queue is empty. The party with the non-empty queue wins and is returned as the result. This approach naturally handles all rounds of the simulation in a single while loop without needing to track round boundaries explicitly.

After winning a duel, the victorious senator participates in the next round of voting. In the circular model, after all n original senators have acted, the survivors repeat in the same relative order. Adding n to the winner's index places them at the correct position in the extended circular sequence — after all current-round senators but in the same relative order among survivors.

This +n trick converts a circular problem into a linear one. Instead of maintaining a circular buffer or resetting indices each round, we simply let indices grow unboundedly. Senators in round 1 have indices 0 to n-1, survivors in round 2 have indices n to 2n-1, and so on. The comparison logic remains the same: smaller index always acts first.

The correctness of this approach follows from the fact that two senators A and B with original indices i < j will always satisfy A's round-2 index (i+n) < B's round-2 index (j+n). The relative ordering is perfectly preserved across rounds, so the greedy comparison by index correctly captures the circular acting order.

Consider "RDD": n=3. Initialize radiant=[0], dire=[1,2]. Round 1, step 1: compare front indices 0 (R) vs 1 (D). Since 0 < 1, Radiant senator 0 wins. Pop both fronts. Re-insert Radiant at 0+3=3. State: radiant=[3], dire=[2].

Round 1, step 2: compare front indices 3 (R) vs 2 (D). Since 2 < 3, Dire senator 2 wins. Pop both fronts. Re-insert Dire at 2+3=5. State: radiant=[], dire=[5]. Radiant queue is now empty — Dire wins! Return "Dire".

Now consider "RD": n=2. radiant=[0], dire=[1]. Compare 0 vs 1: Radiant wins, re-enters at 2. State: radiant=[2], dire=[]. Dire queue empty — return "Radiant". And "RRDDD": radiant=[0,1], dire=[2,3,4]. Step 1: 0<2, R wins, radiant=[1,3], dire=[3,4]. Step 2: 1<3, R wins, radiant=[3,4], dire=[4]. Step 3: 3<4, R wins, radiant=[4,6], dire=[]. Return "Radiant".

Python solution using collections.deque: from collections import deque; def predictPartyVictory(senate: str) -> str: n = len(senate); r = deque(); d = deque(); [r.append(i) if c=="R" else d.append(i) for i, c in enumerate(senate)]; while r and d: ri, di = r.popleft(), d.popleft(); (r if ri < di else d).append((ri if ri < di else di) + n); return "Radiant" if r else "Dire". Time complexity O(n), space complexity O(n) for the two queues.

Java solution: public String predictPartyVictory(String senate) { int n = senate.length(); Queue<Integer> r = new LinkedList<>(), d = new LinkedList<>(); for (int i = 0; i < n; i++) { if (senate.charAt(i) == "R") r.add(i); else d.add(i); } while (!r.isEmpty() && !d.isEmpty()) { int ri = r.poll(), di = d.poll(); if (ri < di) r.add(ri + n); else d.add(di + n); } return r.isEmpty() ? "Dire" : "Radiant"; }. Uses LinkedList as Queue, O(n) time O(n) space.

Both solutions are clean and efficient. The while loop runs at most O(n) total iterations because each iteration eliminates exactly one senator permanently. The total number of re-insertions is bounded by the number of senators in the minority party — once that party is gone, the loop ends. No sorting, no string rebuilding, no inner loops.

Students Unable to Eat Lunch (LeetCode 1700) is a direct relative: students in a queue either take the top sandwich or move to the back of the queue. The problem also involves a circular simulation where greedy counting determines when no progress can be made. Both problems share the theme of modeling a process where order matters and the first feasible action is taken.

Task Scheduler (LeetCode 621) applies greedy logic to CPU scheduling: given tasks with a cooldown period, determine the minimum time to execute all tasks. The greedy strategy is to always schedule the most frequent remaining task, similar to how Dota2 Senate always targets the most immediate threat. Both problems use a frequency-based greedy approach on queues or heaps.

The broader family of greedy simulation problems — Dota2 Senate, Students Lunch, Task Scheduler, Circular Queue design — all share the pattern of maintaining order-sensitive data structures and applying a locally optimal decision at each step. Mastering the index+n re-entry trick for circular simulations is a transferable insight applicable across this entire problem family.