Problem statement

https://leetcode.com/problems/online-election/

Solution

The idea is to precalculate who is winner for all elements in times. The trick is that each moment of time when we have new person idx arriving, winner can be previous winner we have or if cnt[idx] >= votes[1], then we have new winner. In votes we keep tuple (id of winner, number of voices). To get query we need to perfrom binary search.

Complexity

It is O(n + q log n), where n = len(times) and q is number of queries.

Code

class TopVotedCandidate:
    def __init__(self, persons, times):
        self.data = []
        cnt = Counter()
        votes = (-1, 0)
        
        for idx, time in zip(persons, times):
            cnt[idx] += 1
            if cnt[idx] >= votes[1]:
                votes = (idx, cnt[idx])
                
            self.data.append((time, votes[0]))
            
    def q(self, t):
        i = bisect.bisect(self.data, (t, float('inf')))
        return self.data[i-1][1]