# LeetCode 911: Online Election

## Problem Restatement

We need to implement a class called `TopVotedCandidate`.

We are given two arrays:

```python
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

| Item | Meaning |
|---|---|
| Constructor input | `persons` and `times` |
| Query input | A time `t` |
| Query output | Leading candidate at time `t` |
| Tie rule | Most recent vote wins |
| Time array | Strictly increasing |

Class shape:

```python
class TopVotedCandidate:

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

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

## Examples

Example:

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

Queries:

```python
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:

```python
[0]
```

So candidate `0` leads.

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

```python
[0, 1, 1]
```

Candidate `1` leads.

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

```python
[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.

```python
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:

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

When a candidate receives a vote:

```python
count[person] += 1
```

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

```python
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:

```python
i = bisect_right(times, t) - 1
```

Then return:

```python
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

| Operation | Time | Space |
|---|---:|---:|
| Constructor | `O(n)` | `O(n)` |
| `q(t)` | `O(log n)` | `O(1)` |

The constructor stores one leader for each vote.

Each query uses binary search over `times`.

## Implementation

```python
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:

```python
self.times = times
```

We also store the leader after each vote:

```python
self.leaders = []
```

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

```python
count = {}
```

For every vote, update the candidate's count:

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

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

```python
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:

```python
self.leaders.append(leader)
```

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

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

So `i` is the last counted vote index.

Return the precomputed leader:

```python
return self.leaders[i]
```

## Testing

```python
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:

| Test | Why |
|---|---|
| Official-style sequence | Checks normal queries and tie rule |
| Query between vote times | Confirms binary search behavior |
| Query exactly at vote time | Confirms vote at `t` counts |
| Repeated tie changes | Confirms most recent tied candidate wins |