Who is ahead at time t?
Votes come in one at a time. persons[i] receives a vote at time times[i], and times is strictly increasing. At any moment the leader is the person with the most votes so far; when several are tied for the most, the one of them who received a vote most recently leads.
VoteLeader(persons, times) takes all the votes.
leader(t) returns who leads at time t, counting every vote with a time at or before t. It is only called with t no earlier than the first vote.
There can be many calls: aim for O(log n) per call.
- Input
["VoteLeader","leader","leader","leader","leader"]
[[[2,1,1,2,2],[0,4,9,12,20]],[5],[9],[12],[100]]- Output
[null,1,1,2,2]
At time 5, persons 1 and 2 have one vote each and 1 got theirs later, so 1 leads. At 9, person 1 has two. At 12 they tie at two, and 2 got the latest vote.
Limits
1 <= persons.length == times.length <= 50000 <= persons[i] < persons.length0 <= times[i] <= 1000000000, strictly increasingtimes[0] <= t <= 1000000000at most 10000 calls to leader
Hints
Hint 1
The leader can only change when a vote arrives. Work out the leader after every vote once, in the constructor.
Hint 2
For leader(t), binary-search for the last vote time at or before t and return the leader stored for it.
Where this was reported
- Amazon, SDE-1 fixed-term interview, 2025 (LeetCode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
