LeetCode 911: Online Election

Problem Restatement

We need to implement a class called TopVotedCandidate.

We are given two arrays:

persons
times

The i-th vote was cast for persons[i] at time times[i].

For a query time t, we need to return the candidate who was leading at time t.

Votes cast exactly at time t count.

If there is a tie, the candidate who received the most recent vote among the tied candidates wins. This is the key rule of the problem.

Input and Output

Class shape:

class TopVotedCandidate:

    def __init__(self, persons: list[int], times: list[int]):
        ...

    def q(self, t: int) -> int:
        ...

Examples

Example:

persons = [0, 1, 1, 0, 0, 1, 0]
times = [0, 5, 10, 15, 20, 25, 30]

Queries:

q(3)   -> 0
q(12)  -> 1
q(25)  -> 1
q(15)  -> 0
q(24)  -> 0
q(8)   -> 1

At time 3, only the first vote has happened:

[0]

So candidate 0 leads.

At time 12, votes up to time 10 have happened:

[0, 1, 1]

Candidate 1 leads.

At time 25, votes up to time 25 have happened:

[0, 1, 1, 0, 0, 1]

Candidates 0 and 1 both have 3 votes, but candidate 1 received the most recent vote, so candidate 1 leads.

First Thought: Recount Every Query

A direct method is to answer each query from scratch.

For a query t:

1. Count all votes with time <= t.
2. Track the candidate with the highest count.
3. Break ties by the most recent vote.

This works, but it repeats the same counting many times.

class TopVotedCandidate:

    def __init__(self, persons: list[int], times: list[int]):
        self.persons = persons
        self.times = times

    def q(self, t: int) -> int:
        count = {}
        leader = -1
        leader_votes = 0

        for person, time in zip(self.persons, self.times):
            if time > t:
                break

            count[person] = count.get(person, 0) + 1

            if count[person] >= leader_votes:
                leader = person
                leader_votes = count[person]

        return leader

If there are many queries, this is too slow.

Key Insight

The leader only changes when a vote happens.

Between two vote times, the answer stays the same.

So we can precompute the leader after each vote.

Then for query t, we only need to find the latest vote time that is less than or equal to t.

Because times is sorted, we can find that position using binary search.

Preprocessing

During initialization, scan all votes from left to right.

Maintain:

count[candidate] = number of votes
leader = current leading candidate
leader_votes = votes of current leader

When a candidate receives a vote:

count[person] += 1

If this candidate now has at least as many votes as the current leader, update the leader:

if count[person] >= leader_votes:
    leader = person

The >= is important.

It handles ties correctly because the current vote is the most recent vote.

After each vote, store the leader at that time.

Query

For a query time t, find the index of the last vote time <= t.

In Python, this is:

i = bisect_right(times, t) - 1

Then return:

leaders[i]

where leaders[i] is the leader after the i-th vote.

Algorithm

Constructor:

1. Store times.
2. Create an empty vote count map.
3. Create an empty leaders array.
4. Scan each vote.
5. Update that candidate’s vote count.
6. If the candidate ties or beats the current leader, make them the leader.
7. Append the current leader to leaders.

Query:

1. Binary search for the rightmost time <= t.
2. Return the leader stored at that index.

Correctness

After processing vote i, the constructor records the candidate who leads after all votes from 0 through i.

The update rule is correct because a candidate becomes leader when their count is greater than the current leader’s count. If their count is equal, they also become leader because the latest vote wins ties.

For a query time t, all votes with time <= t count, and all later votes do not count.

Since times is strictly increasing, binary search finds exactly the last vote index whose time is at most t.

The stored leader at that index is therefore the leader after exactly the votes that should count for query t.

So q(t) returns the correct candidate.

Complexity

The constructor stores one leader for each vote.

Each query uses binary search over times.

Implementation

from bisect import bisect_right

class TopVotedCandidate:

    def __init__(self, persons: list[int], times: list[int]):
        self.times = times
        self.leaders = []

        count = {}
        leader = -1
        leader_votes = 0

        for person in persons:
            count[person] = count.get(person, 0) + 1

            if count[person] >= leader_votes:
                leader = person
                leader_votes = count[person]

            self.leaders.append(leader)

    def q(self, t: int) -> int:
        i = bisect_right(self.times, t) - 1
        return self.leaders[i]

Code Explanation

We store the vote times for later binary search:

self.times = times

We also store the leader after each vote:

self.leaders = []

The vote count map tracks how many votes each candidate has:

count = {}

For every vote, update the candidate’s count:

count[person] = count.get(person, 0) + 1

Then update the leader if this candidate ties or exceeds the current leader:

if count[person] >= leader_votes:
    leader = person
    leader_votes = count[person]

The >= handles the most recent vote tie rule.

After processing this vote, save the current leader:

self.leaders.append(leader)

For a query, bisect_right gives the insertion position after all times <= t:

i = bisect_right(self.times, t) - 1

So i is the last counted vote index.

Return the precomputed leader:

return self.leaders[i]

Testing

def run_tests():
    top = TopVotedCandidate(
        [0, 1, 1, 0, 0, 1, 0],
        [0, 5, 10, 15, 20, 25, 30],
    )

    assert top.q(3) == 0
    assert top.q(12) == 1
    assert top.q(25) == 1
    assert top.q(15) == 0
    assert top.q(24) == 0
    assert top.q(8) == 1

    top = TopVotedCandidate(
        [1, 2, 2, 1],
        [10, 20, 30, 40],
    )

    assert top.q(10) == 1
    assert top.q(20) == 2
    assert top.q(25) == 2
    assert top.q(40) == 1

    print("all tests passed")

run_tests()

Test meaning: