911. Online Election
Problem Description
The problem presents a scenario where we have a series of votes being cast at certain times for various candidates, represented by the persons
array, where each vote is associated with a timestamp stored in the times
array. We need to track who the leading candidate is at any given point in time, according to the timestamps of votes. When we're asked to find the leader at time t
, we should include votes up to and including t
.
Key points to note:
- Each vote is for
persons[i]
at timetimes[i]
. - A query at time
t
should return the person leading the election at that time. - If there's a tie, the person who received the latest vote (of the tied candidates) is considered the leader.
There are two parts to solving this problem:
- We need a system to track the leading candidate at any time.
- We need an efficient way to answer the query for the leader at a specific time
t
.
We must construct a class TopVotedCandidate
with two methods: a constructor to prepare our data structures for tracking the votes, and a method q(t)
to find the leading candidate at time t
.
Intuition
For the solution, we use two main approaches:
-
Preprocessing the votes in the constructor to know the current leader after each vote is cast.
The intuition here is to iterate through all votes in chronological order and maintain a running count of the votes each person received. A hash map or counter is used to keep track of the votes. We'll keep track of the maximum votes received so far, and whenever a candidate's vote count ties with or exceeds the current max, we update who the current leader is. By doing this, we automatically handle the tiebreaker rule where the most recent vote wins in case of a tie.
To efficiently answer the query later, we create an array (
self.wins
) that holds the leader at the time of each vote cast, and an array (self.times
) which is the same astimes
provided in the input. At the end of the constructor, we have a complete mapping of times to the leader at that point. -
Implementing the query method
q(t)
with a binary search.The reason behind using binary search is that we have a sorted list of times and want to quickly find the last time at or before
t
(as votes are counted up to and including timet
). Binary search allows us to efficiently find this point withO(log n)
complexity, wheren
is the number of votes.Once we perform the binary search in the
self.times
array, we find the index where the time is just equal to or less thant
. We return the corresponding leader fromself.wins
.
Combining these two methods, we can quickly and accurately determine the leading candidate for each query.
Learn more about Binary Search patterns.
Solution Approach
The solution approach utilizes several concepts from computer science, specifically data structures such as hash maps (also referred to as dictionaries or counters in some languages) and algorithms such as binary search.
Here is the breakdown of the implementation:
Constructor: __init__(self, persons: List[int], times: List[int])
-
Initialize Variables:
mx
: A variable to keep track of the maximum number of votes any person has at any point.cur
: A variable to store the person who is currently leading the election.counter
: It's aCounter
object from thecollections
module which acts as a hash map to count votes for each person.self.times
: Stores the times when votes were cast, directly taken from the input.self.wins
: An empty list that we will populate with the person leading after each vote.
-
Count Votes and Record Leaders:
- We loop through
persons
array with indices to access both the person and the corresponding time of the vote. - Each time a person receives a vote, we increment their count in
counter
. - If the person's updated vote count is at least as much as
mx
, we updatemx
to this new count andcur
to the current person. - Then, we append
cur
toself.wins
, which ensures thatself.wins
holds the leader after each vote is cast.
- We loop through
Method: q(self, t: int) -> int
-
- We need to find the latest time that does not exceed
t
inself.times
and get the leading person at that time fromself.wins
. - Initialize
left
to index0
andright
to the last index ofself.wins
. - We execute a loop while
left
is less thanright
to narrow down the search space. - In each iteration, we calculate the middle index,
mid
, using the formula(left + right + 1) >> 1
. The+1
ensures that we favor the right part in the search to find the last occurrence, and>> 1
is a bitwise operation for integer division by 2. - If the time at
mid
is less than or equal tot
, we moveleft
up tomid
since we want to include votes cast at timet
. - If the time at
mid
is greater thant
, we moveright
down tomid - 1
. - The loop continues until
left
andright
converge to a single element which is the largest time less than or equal tot
.
- We need to find the latest time that does not exceed
-
Return the Leader:
- After the loop ends,
left
will point to the required index inself.wins
. - We return
self.wins[left]
as the answer, which gives us the leader at timet
.
- After the loop ends,
This approach ensures that the initialization of the TopVotedCandidate
class preprocesses the votes for quick retrieval, and q
method uses binary search to efficiently answer queries about the leader at any given time t
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Assume we have the following input:
persons
array:[1, 2, 1, 3, 3]
times
array:[0, 10, 20, 30, 40]
When we construct a new TopVotedCandidate
object with the above input, it processes the input arrays as follows:
- Initialize Variables:
mx
is set to0
. It will keep track of the maximum votes received by any candidate.cur
isNone
since initially, no votes have been cast.counter
is an emptyCounter
object.self.times
is set to thetimes
array:[0, 10, 20, 30, 40]
.self.wins
is initialized as an empty list.
- Count Votes and Record Leaders:
- Votes are counted one by one:
- First vote is for person 1 at time 0. We update the counter
{1: 1}
. Since1
>mx
(0),mx
becomes1
andcur
becomes1
.self.wins
is now[1]
. - Second vote is for person 2 at time 10. The counter becomes
{1: 1, 2: 1}
. Since1
(votes for person 2) ≥mx
(1),mx
remains1
andcur
becomes2
due to the most recent vote tiebreaker rule.self.wins
becomes[1, 2]
. - The third vote is for person 1 at time 20. Counter gets updated to
{1: 2, 2: 1}
. Person 1 now has more votes than person 2, somx
is now2
andcur
is1
.self.wins
is now[1, 2, 1]
. - The fourth vote is for person 3 at time 30. The counter is
{1: 2, 2: 1, 3: 1}
. Since person 3's votes1
is not ≥mx
2
,cur
remains1
.self.wins
remains[1, 2, 1]
. - The fifth vote is for person 3 at time 40. The counter updates to
{1: 2, 2: 1, 3: 2}
. Now person 3's votes match the current maximum, but since the vote is the latest, person 3 becomes the leader.self.wins
is now[1, 2, 1, 1, 3]
.
- First vote is for person 1 at time 0. We update the counter
After construction, if we query at time t = 25
, we must find the leader up to that time.
- Binary Search:
- We will run a binary search on
self.times
to find the largest time not exceedingt
. - Initialize
left
to0
andright
to4
(the last index ofself.times
). - The binary search converges, and we find that index
2
(time20
) is the correct index for timet = 25
.
- Return the Leader:
- We observed
self.wins[2]
is1
, so person1
is returned as the leader at timet = 25
.
Constructing the TopVotedCandidate
allowed us to tabulate the leaders efficiently, and querying with a binary search provided us the desired information quickly.
Solution Implementation
1from collections import Counter
2
3class TopVotedCandidate:
4
5 def __init__(self, persons: List[int], times: List[int]):
6 """
7 Initializes the TopVotedCandidate object, preprocesses the leading candidates, and stores for querying later.
8 Args:
9 persons (List[int]): List of people who are voting.
10 times (List[int]): The time at which the persons' votes are cast.
11 """
12 max_votes = current_leader = 0 # Initialize the variables to store maximum votes and current leading candidate.
13 vote_counts = Counter() # A counter to keep track of votes for each candidate.
14 self.times = times # Store the times list for binary search during querying.
15 self.leaders = [] # List to store the leader at each time.
16
17 for index, person in enumerate(persons):
18 vote_counts[person] += 1
19 # Update the current leader if the person has equal or more votes than max_votes.
20 if vote_counts[person] >= max_votes:
21 max_votes, current_leader = vote_counts[person], person
22 # Append the current leader to the leaders list.
23 self.leaders.append(current_leader)
24
25 def q(self, time: int) -> int:
26 """
27 Answer a query to find the top voted candidate at time 't'.
28 Args:
29 time (int): The time at which we want to find the top voted candidate.
30 Returns:
31 int: The candidate who was leading at time 't'.
32 """
33 # Conduct a binary search to find the right-most time that is less than or equal to 'time'.
34 left, right = 0, len(self.leaders) - 1
35 while left < right:
36 mid = (left + right + 1) // 2 # Take the upper middle to prevent infinite loop with two elements.
37 if self.times[mid] <= time:
38 left = mid
39 else:
40 right = mid - 1
41 # Return the leader at the found time.
42 return self.leaders[left]
43
1class TopVotedCandidate {
2 private int[] votingTimes;
3 private int[] leadingCandidates;
4
5 // Constructor to initialize the TopVotedCandidate with persons array and times array.
6 // It calculates the current leading candidate at each voting time.
7 public TopVotedCandidate(int[] persons, int[] times) {
8 int length = persons.length;
9 int maxVotes = 0;
10 int currentLeader = 0;
11 this.votingTimes = times;
12 leadingCandidates = new int[length];
13 int[] voteCounter = new int[length]; // Array to keep track of votes for each person.
14
15 for (int i = 0; i < length; ++i) {
16 int person = persons[i];
17 // Increment vote count for the current person and check if they are the new leader.
18 if (++voteCounter[person] >= maxVotes) {
19 maxVotes = voteCounter[person];
20 currentLeader = person;
21 }
22 leadingCandidates[i] = currentLeader; // Update current leader.
23 }
24 }
25
26 // This method returns the top-voted candidate at a given time `t`.
27 // If `t` is between two times in the votingTimes array, return the top-voted candidate at the latest recorded time before `t`.
28 public int q(int t) {
29 int left = 0;
30 int right = leadingCandidates.length - 1;
31 // Binary search to find the closest time without going over.
32 while (left < right) {
33 int mid = (left + right + 1) >>> 1;
34 if (votingTimes[mid] <= t) {
35 left = mid;
36 } else {
37 right = mid - 1;
38 }
39 }
40 return leadingCandidates[left]; // Return the leader at the found time.
41 }
42}
43
44/**
45 * Your TopVotedCandidate object will be instantiated and called as such:
46 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
47 * int param_1 = obj.q(t);
48 */
49
1#include <vector>
2
3using std::vector;
4
5class TopVotedCandidate {
6public:
7 // Stores the specific times when votes are cast
8 vector<int> voteTimes;
9 // Stores the candidate id with the most votes up to the corresponding time
10 vector<int> leadingCandidates;
11
12 // Constructor
13 TopVotedCandidate(vector<int>& persons, vector<int>& times) : voteTimes(times) {
14 int numberOfVotes = persons.size();
15 leadingCandidates.resize(numberOfVotes);
16 int maxVotes = 0; // Tracks the most votes any candidate has at a certain point
17 int currentWinner = -1; // Tracks the current winning candidate
18 vector<int> votesCount(numberOfVotes, 0); // Counter for the votes each candidate receives
19
20 // Iterate through all the votes
21 for (int i = 0; i < numberOfVotes; ++i) {
22 int personId = persons[i];
23
24 // Increment the corresponding candidate's vote count
25 votesCount[personId]++;
26
27 // Check if the current candidate has equal to or more votes than the max
28 if (votesCount[personId] >= maxVotes) {
29 maxVotes = votesCount[personId]; // Update the max votes
30 currentWinner = personId; // Update the current winner
31 }
32
33 // Record the leading candidate at the ith time
34 leadingCandidates[i] = currentWinner;
35 }
36 }
37
38 // Returns the candidate id that was leading at time t.
39 int q(int t) {
40 // Binary search for the right index because the votes are recorded in time order
41 int left = 0;
42 int right = leadingCandidates.size() - 1;
43 while (left < right) {
44 int mid = (left + right + 1) / 2;
45 if (voteTimes[mid] <= t) {
46 left = mid; // Mid is a valid position, move left up to mid
47 } else {
48 right = mid - 1; // Mid is not valid, search in the left section
49 }
50 }
51 // Once the binary search finishes, 'left' will point at the largest time <= t
52 return leadingCandidates[left];
53 }
54};
55
56/**
57 * Your TopVotedCandidate object will be instantiated and called as such:
58 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
59 * int result = obj->q(t);
60 */
61
1// Requires TypeScript's support for tuples, features introduced in ES6, and ES6 map objects
2
3// Declare global variables to maintain the state
4let voteTimes: number[] = [];
5let leadingCandidates: number[] = [];
6let votesCount: Map<number, number> = new Map(); // Using a Map to count votes for scalability
7let maxVotes: number = 0;
8let currentWinner: number = -1;
9
10// Initialize the state with the persons and times array
11function initialize(persons: number[], times: number[]): void {
12 voteTimes = times;
13 for (let i = 0; i < persons.length; ++i) {
14 votesCount.set(persons[i], 0);
15 }
16 leadingCandidates = new Array(times.length).fill(-1);
17}
18
19// Processes the votes and updates the state
20function processVotes(persons: number[]): void {
21 persons.forEach((personId, i) => {
22 let count = votesCount.get(personId) || 0;
23 votesCount.set(personId, count + 1);
24
25 if (count + 1 >= maxVotes) {
26 maxVotes = count + 1;
27 currentWinner = personId;
28 }
29
30 leadingCandidates[i] = currentWinner;
31 });
32}
33
34// Function to initialize, it emulates the constructor logic
35function topVotedCandidate(persons: number[], times: number[]): void {
36 initialize(persons, times);
37 processVotes(persons);
38}
39
40// Function that emulates the q method in the original class
41function q(t: number): number {
42 let left = 0;
43 let right = leadingCandidates.length - 1;
44
45 while (left < right) {
46 let mid = Math.floor((left + right + 1) / 2);
47 if (voteTimes[mid] <= t) {
48 left = mid;
49 } else {
50 right = mid - 1;
51 }
52 }
53
54 return leadingCandidates[left];
55}
56
57// Example of usage
58let persons = [0, 1, 1, 0, 0, 1, 0];
59let times = [0, 5, 10, 15, 20, 25, 30];
60topVotedCandidate(persons, times); // Initialize state
61console.log(q(3)); // Should return the candidate id that was leading at time 3
62console.log(q(12)); // Should return the candidate id that was leading at time 12
63
Time and Space Complexity
Time Complexity:
-
The
__init__
method has a time complexity ofO(N)
whereN
is the number of votes (the length of thepersons
andtimes
lists). This accounts for iterating over all the votes once and updating the counter each time. -
The
q
method performs a binary search which has a time complexity ofO(log N)
, whereN
is the number of elements inself.times
orself.wins
since both lists are of the same length.
Space Complexity:
-
The space complexity of the
__init__
method isO(N)
whereN
is the number of votes. This is because we store two lists,self.times
andself.wins
, both of which containN
elements. Additionally, there is a counter that in the worst-case scenario could have as many keys as there are votes, therefore its size is alsoO(N)
. -
The
q
method does not use any additional space other than a few variables for the binary search, which means its space complexity isO(1)
as it does not depend on the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!