# Online Election
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/online-election)
Canonical: https://scaleengineer.com/dsa/problems/online-election
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [CARS24](https://scaleengineer.com/companies/cars24)
---
## Problem
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 <= 5000`
* `times.length == persons.length`
* `0 <= persons[i] < persons.length`
* `0 <= times[i] <= 109`
* `times` is sorted in a strictly increasing order.
* `times[0] <= t <= 109`
* At most `104` calls will be made to `q`.

# Approaches
## Brute Force Simulation per Query
This straightforward approach simulates the election from the beginning up to the query time `t` for every single query. The constructor's role is minimal, simply storing the initial data. While easy to conceptualize, it's inefficient for numerous queries.
**Time:** O(N * Q), where N is the number of votes and Q is the number of queries. Each query involves a binary search (O(log N)) followed by a loop that can run up to N times (O(N)). Thus, each query is O(N), leading to a total time of O(N * Q). · **Space:** O(P) for each query, where P is the number of unique persons (P <= N). This space is for the `counts` map used during the simulation within each query.
**Pros:** Simple to understand and implement.; The constructor is very fast, O(1).
**Cons:** Highly inefficient for a large number of queries.; Repeats the same counting work for overlapping time intervals.; Likely to result in a 'Time Limit Exceeded' error in a competitive programming context.
### Explanation
In this method, we avoid any pre-computation and handle all the logic within the `q(t)` function.

The constructor `TopVotedCandidate(int[] persons, int[] times)` just saves the input arrays for later use.

The query function `q(int t)` performs the following steps:
1.  It first determines how many votes to consider. Given the query time `t`, it finds the index `k` of the last vote cast at or before `t`. This can be done efficiently with a binary search on the sorted `times` array.
2.  It then simulates the election up to vote `k`. A hash map is used to keep track of the vote count for each person.
3.  It iterates through the votes from index `0` to `k`. For each vote `i`, it increments the count for `persons[i]`.
4.  To correctly handle the tie-breaking rule (the most recent vote wins), it also keeps track of the current leader. After updating a person's vote count, if their new count is greater than or equal to the current leader's count, they become the new leader. The 'greater than or equal' condition elegantly handles ties by favoring the person who just voted.
5.  After processing all votes up to index `k`, the final leader is returned as the result.

```java
import java.util.HashMap;
import java.util.Map;

class TopVotedCandidate {
    int[] persons;
    int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.persons = persons;
        this.times = times;
    }

    public int q(int t) {
        // Find the index of the last vote at or before time t using binary search.
        int low = 0, high = times.length - 1;
        int lastVoteIndex = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (times[mid] <= t) {
                lastVoteIndex = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        if (lastVoteIndex == -1) {
            return -1; // Should not happen based on constraints
        }

        // Simulate the election up to this point
        Map<Integer, Integer> counts = new HashMap<>();
        int leader = -1;
        int maxVotes = 0;

        for (int i = 0; i <= lastVoteIndex; i++) {
            int person = persons[i];
            counts.put(person, counts.getOrDefault(person, 0) + 1);
            
            if (counts.get(person) >= maxVotes) {
                maxVotes = counts.get(person);
                leader = person;
            }
        }
        return leader;
    }
}
```
### Algorithm
- In the constructor, store the `persons` and `times` arrays.
- In the `q(t)` method:
  - Find the largest index `k` in `times` such that `times[k] <= t` using binary search.
  - Initialize an empty map `counts` for vote tallies.
  - Initialize `leader = -1` and `maxVotes = 0`.
  - Loop from `i = 0` to `k`:
    - Increment the vote count for `persons[i]` in the `counts` map.
    - If the new count for `persons[i]` is greater than or equal to `maxVotes`, update `leader` to `persons[i]` and `maxVotes` to the new count.
  - Return the final `leader`.

## Precomputation of Leaders with Binary Search
This optimized approach is based on the insight that the election leader can only change when a vote is cast. We can pre-calculate the leader at each of these specific time points and store them. Queries can then be answered very quickly by finding the relevant time point using binary search and retrieving the precomputed leader.
**Time:** O(N + Q * log N). The constructor takes O(N) time to iterate through all votes and precompute leaders. Each of the Q queries takes O(log N) time for the binary search. · **Space:** O(N). We need O(N) space for the `leaders` array and to store the `times` array. The `counts` map used during precomputation also requires O(P) space, where P is the number of unique persons (P <= N).
**Pros:** Extremely fast query time, making it suitable for a large number of queries.; The expensive computation is performed only once.; Overall efficient solution that passes strict time limits.
**Cons:** Requires O(N) extra space to store precomputed results.; The constructor has a higher upfront cost (O(N)) compared to the brute-force approach.
### Explanation
The core idea is to trade a one-time computation cost in the constructor for extremely fast queries.

**Constructor `TopVotedCandidate(int[] persons, int[] times)`:**
1.  We precompute the leader at every time `t` present in the `times` array.
2.  We use an array, `leaders`, of the same size as `persons` to store the leader at each corresponding time in `times`.
3.  We iterate through the votes chronologically from `i = 0` to `n-1`. We use a hash map `counts` to maintain a running tally of votes for each person.
4.  We also track the current `leader` and their `maxVotes`. At each step `i`, we process the vote for `persons[i]`, update their count, and check if they become the new leader. A person `p` becomes the leader if their vote count surpasses the current `maxVotes`, or if it equals `maxVotes` (due to the tie-breaking rule favoring the most recent vote).
5.  The leader at time `times[i]` is then stored in `leaders[i]`.

**Query `q(int t)`:**
1.  For a query time `t`, the leader is the same as the leader at the time of the last vote cast at or before `t`.
2.  Our goal is to find the largest index `i` such that `times[i] <= t`.
3.  Since the `times` array is sorted, we can perform a binary search on it to find this index `i` in logarithmic time.
4.  Once index `i` is found, the answer is simply the precomputed value `leaders[i]`.

```java
import java.util.HashMap;
import java.util.Map;

class TopVotedCandidate {
    private int[] leaders;
    private int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        int n = persons.length;
        this.leaders = new int[n];
        
        Map<Integer, Integer> counts = new HashMap<>();
        int leader = -1;
        int maxVotes = 0;

        for (int i = 0; i < n; i++) {
            int p = persons[i];
            counts.put(p, counts.getOrDefault(p, 0) + 1);
            
            if (counts.get(p) >= maxVotes) {
                maxVotes = counts.get(p);
                leader = p;
            }
            leaders[i] = leader;
        }
    }

    public int q(int t) {
        // Binary search to find the index of the latest time <= t
        int low = 0, high = times.length - 1;
        int ansIdx = 0; // The index of the leader

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (times[mid] <= t) {
                ansIdx = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return leaders[ansIdx];
    }
}
```
### Algorithm
- In the constructor:
  - Initialize a `leaders` array, a `counts` map, `leader = -1`, and `maxVotes = 0`.
  - Loop from `i = 0` to `n-1`:
    - Update the vote count for `persons[i]`.
    - If `persons[i]`'s new count is `>= maxVotes`, update `leader` and `maxVotes`.
    - Store the current `leader` in `leaders[i]`.
- In the `q(t)` method:
  - Use binary search on the `times` array to find the largest index `i` where `times[i] <= t`.
  - Return `leaders[i]`.

# Solutions
### Java

```java
class TopVotedCandidate { private int [] times ; private int [] wins ; public TopVotedCandidate ( int [] persons , int [] times ) { int n = persons . length ; int mx = 0 , cur = 0 ; this . times = times ; wins = new int [ n ]; int [] counter = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { int p = persons [ i ]; if (++ counter [ p ] >= mx ) { mx = counter [ p ]; cur = p ; } wins [ i ] = cur ; } } public int q ( int t ) { int left = 0 , right = wins . length - 1 ; while ( left < right ) { int mid = ( left + right + 1 ) >>> 1 ; if ( times [ mid ] <= t ) { left = mid ; } else { right = mid - 1 ; } } return wins [ left ]; } } /** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate obj = new TopVotedCandidate(persons, times); * int param_1 = obj.q(t); */
```

### CPP

```cpp
class TopVotedCandidate { public: vector < int > times ; vector < int > wins ; TopVotedCandidate ( vector < int >& persons , vector < int >& times ) { int n = persons . size (); wins . resize ( n ); int mx = 0 , cur = 0 ; this -> times = times ; vector < int > counter ( n ); for ( int i = 0 ; i < n ; ++ i ) { int p = persons [ i ]; if ( ++ counter [ p ] >= mx ) { mx = counter [ p ]; cur = p ; } wins [ i ] = cur ; } } int q ( int t ) { int left = 0 , right = wins . size () - 1 ; while ( left < right ) { int mid = left + right + 1 >> 1 ; if ( times [ mid ] <= t ) left = mid ; else right = mid - 1 ; } return wins [ left ]; } }; /** * Your TopVotedCandidate object will be instantiated and called as such: * TopVotedCandidate* obj = new TopVotedCandidate(persons, times); * int param_1 = obj->q(t); */
```

### Python

```python
class TopVotedCandidate : def __init__ ( self , persons : List [ int ], times : List [ int ]): mx = cur = 0 counter = Counter () self . times = times self . wins = [] for i , p in enumerate ( persons ): counter [ p ] += 1 if counter [ p ] >= mx : mx , cur = counter [ p ], p self . wins . append ( cur ) def q ( self , t : int ) -> int : left , right = 0 , len ( self . wins ) - 1 while left < right : mid = ( left + right + 1 ) >> 1 if self . times [ mid ] <= t : left = mid else : right = mid - 1 return self . wins [ left ] # Your TopVotedCandidate object will be instantiated and called as such: # obj = TopVotedCandidate(persons, times) # param_1 = obj.q(t)
```