Solution


Intuition and Algorithm

We can store the votes in a list A of lists of votes. Each vote has a person and a timestamp, and A[count] is a list of the count-th votes received for that person.

Then, A[i][0] and A[i] are monotone increasing, so we can binary search on them to find the most recent vote by time.

Complexity Analysis

  • Time Complexity: , where is the number of votes, and is the number of queries.

  • Space Complexity: .


Intuition and Algorithm

As the votes come in, we can remember every event (winner, time) when the winner changes. After, we have a sorted list of these events that we can binary search for the answer.

Complexity Analysis

  • Time Complexity: , where is the number of votes, and is the number of queries.

  • Space Complexity: .


Analysis written by: @awice.