Online Election
Online Election is a medium binary search problem solved with the bisect pattern.
The best approach, optimal (precompute leaders + binary search), runs in O(n) build, O(log n) per query time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recount for every query) up.
Problem
An election records each vote as it happens: the i-th vote went to candidate persons[i] at time times[i], and the times are strictly increasing.
Implement TopVotedCandidate:
TopVotedCandidate(int[] persons, int[] times)stores the votes.int q(int t)returns the candidate who was leading at timet, counting every vote cast at or beforet.
The leader is the candidate with the most votes. If several candidates are tied for the most votes, the one who received the most recent of those votes leads.
Examples
Example 1
- Input
TopVotedCandidate([2, 1, 1, 2, 2, 0], [0, 4, 9, 15, 20, 30]), q(3), q(4), q(9), q(16), q(40)- Output
2, 1, 1, 2, 2- Why
- At time 4 candidates 2 and 1 have one vote each and 1 voted last, so 1 leads. At time 16 they have two each and the latest vote went to 2.
Example 2
- Input
TopVotedCandidate([0, 1, 2], [5, 6, 7]), q(5), q(6), q(7), q(100)- Output
0, 1, 2, 2- Why
- Every candidate has one vote, so the leader is always whoever received the most recent vote.
Constraints
1 <= persons.length <= 5000andtimes.length == persons.length0 <= persons[i] < persons.length0 <= times[i] <= 10^9andtimesis strictly increasing.times[0] <= t <= 10^9for every query.- At most
10^4calls toq.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recount for every query) | O(n) per query | O(n) |
| Optimal (precompute leaders + binary search) | O(n) build, O(log n) per query | O(n) |
1Brute force (recount for every query)
O(n) per queryEach query replays up to n votes.O(n)The stored votes and one count array of size n.Keep the raw votes. For each query, replay all votes cast at or before t from scratch, keeping counts and the current leader, and return the leader at the end.
- Store
personsandtimesin the constructor. - q(t): reset a count array; for every vote with
times[i] <= t, increase its count and make it the leader if its count is at least the leader's count. - Return the leader.
class TopVotedCandidate {
private final int[] persons, times;
public TopVotedCandidate(int[] persons, int[] times) {
this.persons = persons;
this.times = times;
}
public int q(int t) {
int[] count = new int[persons.length];
int leader = -1;
for (int i = 0; i < persons.length && times[i] <= t; i++) {
int p = persons[i];
count[p]++;
if (leader == -1 || count[p] >= count[leader]) leader = p;
}
return leader;
}
}class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
self.persons = persons
self.times = times
def q(self, t: int) -> int:
count = [0] * len(self.persons)
leader = -1
for i in range(len(self.persons)):
if self.times[i] > t:
break
p = self.persons[i]
count[p] += 1
if leader == -1 or count[p] >= count[leader]:
leader = p
return leaderclass TopVotedCandidate {
vector<int> persons, times;
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) : persons(persons), times(times) {}
int q(int t) {
vector<int> count(persons.size(), 0);
int leader = -1;
for (size_t i = 0; i < persons.size() && times[i] <= t; i++) {
int p = persons[i];
count[p]++;
if (leader == -1 || count[p] >= count[leader]) leader = p;
}
return leader;
}
};class TopVotedCandidate {
constructor(persons, times) {
this.persons = persons;
this.times = times;
}
q(t) {
const count = new Array(this.persons.length).fill(0);
let leader = -1;
for (let i = 0; i < this.persons.length && this.times[i] <= t; i++) {
const p = this.persons[i];
count[p]++;
if (leader === -1 || count[p] >= count[leader]) leader = p;
}
return leader;
}
}2Optimal (precompute leaders + binary search)
O(n) build, O(log n) per queryThe constructor replays the n votes once; every query is one binary search.O(n)Arrays of n times, n leaders and n counts.Replay the votes once in the constructor and record leader[i], the leader right after vote i. A query at time t is answered by the last vote cast at or before t: binary search times for the largest index with times[i] <= t and return leader[i].
- Constructor: keep counts; after each vote, update the leader if the new candidate's count is at least the leader's count, and store it in
leader[i]. - q(t): binary search for the largest
iwithtimes[i] <= t(it exists becauset >= times[0]). - Return
leader[i].
class TopVotedCandidate {
private final int[] times, leader;
public TopVotedCandidate(int[] persons, int[] times) {
int n = persons.length;
this.times = times;
this.leader = new int[n];
int[] count = new int[n];
int cur = -1;
for (int i = 0; i < n; i++) {
int p = persons[i];
count[p]++;
if (cur == -1 || count[p] >= count[cur]) cur = p;
leader[i] = cur;
}
}
public int q(int t) {
int lo = 0, hi = times.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (times[mid] <= t) lo = mid;
else hi = mid - 1;
}
return leader[lo];
}
}class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
n = len(persons)
self.times = times
self.leader = [0] * n
count = [0] * n
cur = -1
for i, p in enumerate(persons):
count[p] += 1
if cur == -1 or count[p] >= count[cur]:
cur = p
self.leader[i] = cur
def q(self, t: int) -> int:
lo, hi = 0, len(self.times) - 1
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if self.times[mid] <= t:
lo = mid
else:
hi = mid - 1
return self.leader[lo]class TopVotedCandidate {
vector<int> times, leader;
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
int n = persons.size();
leader.assign(n, 0);
vector<int> count(n, 0);
int cur = -1;
for (int i = 0; i < n; i++) {
int p = persons[i];
count[p]++;
if (cur == -1 || count[p] >= count[cur]) cur = p;
leader[i] = cur;
}
}
int q(int t) {
int lo = 0, hi = times.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (times[mid] <= t) lo = mid;
else hi = mid - 1;
}
return leader[lo];
}
};class TopVotedCandidate {
constructor(persons, times) {
const n = persons.length;
this.times = times;
this.leader = new Array(n).fill(0);
const count = new Array(n).fill(0);
let cur = -1;
for (let i = 0; i < n; i++) {
const p = persons[i];
count[p]++;
if (cur === -1 || count[p] >= count[cur]) cur = p;
this.leader[i] = cur;
}
}
q(t) {
let lo = 0, hi = this.times.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo + 1) / 2);
if (this.times[mid] <= t) lo = mid;
else hi = mid - 1;
}
return this.leader[lo];
}
}Edge cases to test
- A query exactly at a vote time includes that vote
- A query between two votes uses the state after the earlier one
- A query after the last vote returns the final leader
- A tie in vote counts goes to the candidate who received the latest vote, even if the other candidate reached that count first
- A single vote: every query returns that candidate
Hints
Hint 1
The leader can only change when a vote is cast, so there are at most n different moments to know about.
Hint 2
Walk through the votes once, keeping counts and the current leader. After vote i, the leader is the new candidate if their count is at least the old leader's count (ties go to the latest vote).
Hint 3
Store leader[i] for every vote. A query t needs the last vote with times[i] <= t, which a binary search over times finds in O(log n).
FAQ
What is the best time complexity for Online Election?
Optimal (precompute leaders + binary search) runs in O(n) build, O(log n) per query time and O(n) extra space. The constructor replays the n votes once; every query is one binary search.
Which pattern does Online Election use?
It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.
Is there a brute force solution for Online Election?
Yes. Brute force (recount for every query) takes O(n) per query time and O(n) space. Keep the raw votes.
Which edge cases should I test for Online Election?
A query exactly at a vote time includes that vote; A query between two votes uses the state after the earlier one; A query after the last vote returns the final leader; A tie in vote counts goes to the candidate who received the latest vote, even if the other candidate reached that count first; A single vote: every query returns that candidate.