Online Election

Med

#0865Time: 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.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

You are given two integer arrays persons and times. In an election, the i^th 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] <= 10⁹
times is sorted in a strictly increasing order.
times[0] <= t <= 10⁹
At most 10⁴ calls will be made to q.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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.
It then simulates the election up to vote k. A hash map is used to keep track of the vote count for each person.
It iterates through the votes from index 0 to k. For each vote i, it increments the count for persons[i].
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.
After processing all votes up to index k, the final leader is returned as the result.

1import java.util.HashMap;2import java.util.Map;3 4class TopVotedCandidate {5    int[] persons;6    int[] times;7 8    public TopVotedCandidate(int[] persons, int[] times) {9        this.persons = persons;10        this.times = times;11    }12 13    public int q(int t) {14        // Find the index of the last vote at or before time t using binary search.15        int low = 0, high = times.length - 1;16        int lastVoteIndex = -1;17        while (low <= high) {18            int mid = low + (high - low) / 2;19            if (times[mid] <= t) {20                lastVoteIndex = mid;21                low = mid + 1;22            } else {23                high = mid - 1;24            }25        }26 27        if (lastVoteIndex == -1) {28            return -1; // Should not happen based on constraints29        }30 31        // Simulate the election up to this point32        Map<Integer, Integer> counts = new HashMap<>();33        int leader = -1;34        int maxVotes = 0;35 36        for (int i = 0; i <= lastVoteIndex; i++) {37            int person = persons[i];38            counts.put(person, counts.getOrDefault(person, 0) + 1);39            40            if (counts.get(person) >= maxVotes) {41                maxVotes = counts.get(person);42                leader = person;43            }44        }45        return leader;46    }47}

Complexity

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.

Trade-offs

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.

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.

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].

Walkthrough

The core idea is to trade a one-time computation cost in the constructor for extremely fast queries.

Constructor TopVotedCandidate(int[] persons, int[] times):

We precompute the leader at every time t present in the times array.
We use an array, leaders, of the same size as persons to store the leader at each corresponding time in times.
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.
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).
The leader at time times[i] is then stored in leaders[i].

Query q(int t):

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.
Our goal is to find the largest index i such that times[i] <= t.
Since the times array is sorted, we can perform a binary search on it to find this index i in logarithmic time.
Once index i is found, the answer is simply the precomputed value leaders[i].

1import java.util.HashMap;2import java.util.Map;3 4class TopVotedCandidate {5    private int[] leaders;6    private int[] times;7 8    public TopVotedCandidate(int[] persons, int[] times) {9        this.times = times;10        int n = persons.length;11        this.leaders = new int[n];12        13        Map<Integer, Integer> counts = new HashMap<>();14        int leader = -1;15        int maxVotes = 0;16 17        for (int i = 0; i < n; i++) {18            int p = persons[i];19            counts.put(p, counts.getOrDefault(p, 0) + 1);20            21            if (counts.get(p) >= maxVotes) {22                maxVotes = counts.get(p);23                leader = p;24            }25            leaders[i] = leader;26        }27    }28 29    public int q(int t) {30        // Binary search to find the index of the latest time <= t31        int low = 0, high = times.length - 1;32        int ansIdx = 0; // The index of the leader33 34        while (low <= high) {35            int mid = low + (high - low) / 2;36            if (times[mid] <= t) {37                ansIdx = mid;38                low = mid + 1;39            } else {40                high = mid - 1;41            }42        }43        return leaders[ansIdx];44    }45}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class 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); */

1class 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); */

1class 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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem