You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i].

For each query at a time t, find the person that was leading the election at time t. Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Implement the TopVotedCandidate class:


	TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
	int q(int t) Returns the number of the person that was leading the election at time t according to the mentioned rules.


&nbsp;
Example 1:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

Explanation
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // return 0, At time 3, the votes are [0], and 0 is leading.
topVotedCandidate.q(12); // return 1, At time 12, the votes are [0,1,1], and 1 is leading.
topVotedCandidate.q(25); // return 1, At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
topVotedCandidate.q(15); // return 0
topVotedCandidate.q(24); // return 0
topVotedCandidate.q(8); // return 1



&nbsp;
Constraints:


	1 &lt;= persons.length &lt;= 5000
	times.length == persons.length
	0 &lt;= persons[i] &lt; persons.length
	0 &lt;= times[i] &lt;= 109
	times is sorted in a strictly increasing order.
	times[0] &lt;= t &lt;= 109
	At most 104 calls will be made to q.


class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        counter = defaultdict(int)

        mostVotePersons = [0] * len(persons) # mostVotePersons[i] is the most vote person at times[i]
        largestVote = -1 # keep largest vote person index
        for i in range(len(persons)):
            counter[persons[i]] += 1
            if largestVote == -1 or counter[persons[i]] >= counter[largestVote]:
                largestVote = persons[i]
            mostVotePersons[i] = largestVote
        
        self.times = times
        self.mostVotePersons = mostVotePersons

    def q(self, t: int) -> int:
        idx = bisect_right(self.times, t) - 1 # binary search on times to find the most recent time before t
        return self.mostVotePersons[idx]
class TopVotedCandidate {
    int[] persons;
    int[] times;
    int length;
    Map<Integer, Integer> voteCount;
    Map<Integer, Integer> voteLead;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.persons = persons;
        this.times = times;
        length = times.length-1;
        int leadCount = 0;
        int leadPerson = -1;
        voteCount = new HashMap<>();
        voteLead = new HashMap<>();
        for(int i=0; i<=length; i++){
            int newCount = voteCount.getOrDefault(persons[i], 0) + 1;
            voteCount.put(persons[i], newCount);
            if(newCount >= leadCount){
                leadCount = newCount;
                leadPerson = persons[i];
            }
            voteLead.put(times[i], leadPerson);
        }
    }

    public int q(int t) {
        int leadPerson = -1;
        if(voteLead.containsKey(t)) {
            leadPerson = voteLead.get(t);
        }
        else if(t < times[0]){
            leadPerson = voteLead.get(times[0]);
        }
        else if(t > times[length]){
            leadPerson = voteLead.get(times[length]);
        }
        else {
            int low = 0;
            int high = length;
            while(low <= high){
                int mid = low + (high-low)/2;
                if(times[mid] > t) high = mid - 1;
                else low = mid + 1;
            }
            leadPerson = voteLead.get(times[high]);
        }
        return leadPerson;
    }
}
class TopVotedCandidate {
public:
    vector<int> pref;
    vector<int> glob_times;
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int n = times.size();
        glob_times = times;
        pref.resize(n);
        vector<int> cnt;
        int sz = persons.size();
        cnt.resize(sz+1, 0);
        cnt[persons[0]]++;
        pref[0] = persons[0];
        int maxi = 1;
        int maxi_person = persons[0];
        for(int i = 1; i < n; i++){            
            cnt[persons[i]]++;
            if(cnt[persons[i]] > maxi){
                maxi = cnt[persons[i]];
                maxi_person = persons[i];
            }
            else if(cnt[persons[i]] == maxi){
                maxi_person = persons[i];
            }
            
            pref[i] = maxi_person;
        }
    } 
    
    int q(int t) {
        
        int it = upper_bound(glob_times.begin(), glob_times.end(), t) - glob_times.begin();
        if(it == 0) it++;
        return pref[it-1];
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */
var TopVotedCandidate = function(persons, times) {
    this.times = times;
    this.len = times.length;
    this.votes = new Array(this.len).fill(0);
    
    let max = 0; // max votes received by any single candidate so far.
    let leader = -1l;
    
    this.leaders = persons.map((person, i) => {
        this.votes[person]++;
        
        if (this.votes[person] >= max) {
            max = this.votes[person];
            leader = person;
        }
        
        return leader;
    });
    
};

TopVotedCandidate.prototype.q = function(t) {
    let left = 0;
    let right = this.len - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (this.times[mid] === t) return this.leaders[mid];
        else if (this.times[mid] < t) left = mid + 1;
        else right = mid - 1;
    }
	
    return this.leaders[right];
};
Online Election