Dota2 Senate - Solution & Explanation

Problem Overview: You are given a string where each character represents a senator from the Radiant (R) or Dire (D) party. Senators take turns banning opponents. Once banned, a senator cannot vote in future rounds. The process continues in rounds until only one party remains with active senators. Your task is to predict which party wins.

Approach 1: Direct Round Simulation (O(n^2) time, O(n) space)

The most straightforward idea is to simulate the voting rounds exactly as described. Iterate through the string in a circular manner. When a senator appears, check whether they still have the right to vote. If so, ban the next available opponent by marking them inactive. Continue looping until all remaining active senators belong to the same party.

This approach mirrors the problem statement but repeatedly scans the array to find the next valid opponent. In the worst case, each senator might trigger a long search across the list. That repeated scanning pushes the time complexity to O(n^2). The space cost stays O(n) because you maintain the senate state and banned markers.

Approach 2: Queue Simulation with Indices (O(n) time, O(n) space)

The optimized strategy treats the process as a turn-based competition using two queues. Store the indices of Radiant senators in one queue and Dire senators in another. Each round compares the front elements of both queues. The senator with the smaller index acts first and bans the opponent.

After banning, the acting senator returns to the queue with an updated index of currentIndex + n. This represents the next round because the senate order wraps around. The banned senator simply disappears from the process. Continue until one queue becomes empty.

This method avoids scanning for opponents. Each senator enters and leaves the queue a limited number of times, giving an overall time complexity of O(n) and space complexity of O(n). The behavior is essentially a greedy turn scheduling problem using a queue. The input itself is a string, and the decision rule follows a greedy principle: whoever appears earlier in the current round gets priority to ban.

Recommended for interviews: Interviewers typically expect the queue simulation approach. The brute-force round simulation shows that you understand the mechanics of the problem, but the index-based queue solution demonstrates stronger algorithmic thinking. It converts a circular voting process into a clean greedy scheduling problem and reduces the complexity from quadratic to linear.