Solution
Approach 1: List of Lists + Binary Search
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: .
Approach 2: Precomputed Answer + Binary Search
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.