< Back




649. Dota2 Senate

Problem based off of the Dota2 game. We have a group of senators that can vote with two options, to
ban another senator to vote during their turn, or to declare victory when no senators of the
opposite party remain. The senators vote optimally to ensure their party wins.

Because voting happens in multiple rounds in a round robin fashion, we can best solve this problem
by using a queue. We process the senators one by one, but we don't know what party the next senator
is going to be in. We know, however, that the current senator will vote to ban an opposing senator.
Thus, when we pop a senator off the queue from the left, we maintain a floating ban semaphore. This
semaphore denotes whether or not a previous semaphore has voted to ban senators of this current
party.

If the floating ban flag is set, the current senator is removed from the queue, banned from voting
in future rounds, else, the senator is added to the end of the queue to vote in the next round and
the floating ban semaphore for the opposing party is incremented.

We continue to eliminate senators in this fashion until no more senators remain from one of the two
parties.

The solution is as follows:


  from collections import deque

  class Solution:
      def predictPartyVictory(self, senate: str) -> str:
          queue = deque(senate)
          r_count = d_count = 0
          r_floating_ban = d_floating_ban = 0

          for senator in senate:
              if senator == "R":
                  r_count += 1
              else:
                  d_count += 1

          while r_count > 0 and d_count > 0:
              senator = queue.popleft()

              if senator == "R":
                  if r_floating_ban:
                      r_floating_ban -= 1
                      r_count -= 1
                  else:
                      d_floating_ban += 1
                      queue.append(senator)
              else:
                  if d_floating_ban:
                      d_floating_ban -= 1
                      d_count -= 1
                  else:
                      r_floating_ban += 1
                      queue.append(senator)

          return "Radiant" if r_count else "Dire"


_ Time Complexity:

  O(n) - We count all the senators and we also process all senators in a queue.

_ Space Complexity:

  O(n) - We maintain a queue to schedule round robin voting.