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.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
Constraints:
1 <= persons.length <= 5000times.length == persons.length0 <= persons[i] < persons.length0 <= times[i] <= 109times is sorted in a strictly increasing order.times[0] <= t <= 109104 calls will be made to q.The key idea in #911 Online Election is to efficiently determine who was leading the vote at a given time. During preprocessing, iterate through the votes and maintain a running vote count using a hash map. Track the current leader after each vote; if a candidate's vote count becomes greater than or equal to the current leader, update the leader to that candidate. Store this leader in an array corresponding to each vote time.
To answer queries, we are given a time t. Since the vote times are sorted, we can apply binary search to find the latest vote that occurred at or before t. The leader stored at that index represents the winner at that moment. This design separates preprocessing from querying, making repeated queries efficient.
The preprocessing step runs once, while each query can be answered quickly using binary search, making the approach scalable for many queries.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Preprocessing votes and tracking leaders | O(n) | O(n) |
| Query using Binary Search | O(log n) | O(1) |
take U forward
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Online Election are common in FAANG-style interviews because they test design thinking, preprocessing strategies, and efficient querying using binary search and hash maps.
Binary search is used because the vote times are strictly increasing. It helps quickly locate the latest vote that occurred before or at the query time, reducing query time to O(log n).
A combination of arrays and a hash map works best. The hash map keeps track of vote counts for each candidate, while arrays store the leader at each vote time to allow fast lookups with binary search.
The optimal approach preprocesses the votes to track the leading candidate after each vote. For queries, binary search is used to find the most recent vote time less than or equal to the query time, and the stored leader is returned.