Online Election — Solution in Python, Java & C++
Online Election solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
Online Election is a medium coding problem on arrays, hash table and binary search, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Binary Search
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An election records its votes as they arrive: the i-th vote went to candidate persons[i] at time times[i], and the times are strictly increasing.
Write the class TopVotedCandidate:
TopVotedCandidate(int[] persons, int[] times)stores the votes.int q(int t)returns the candidate who was leading at timet— the one with the most votes among the votes cast at or beforet. A vote cast exactly attcounts. If several candidates are tied for the most votes, the one among them who received a vote most recently leads.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["TopVotedCandidate","q","q","q","q","q"]
[[[0,1,1,0,0,1],[0,4,9,15,22,30]],[3],[9],[16],[25],[30]]
Output: [null,0,1,0,0,1]
Explanation: By time 3 only candidate 0 has a vote. At time 9 the counts are 0:1, 1:2, so 1 leads. At 16 they are 2:2 and candidate 0 voted last, so 0 leads; at 25 candidate 0 has 3. At 30 it is 3:3 again and the latest vote went to 1.
Example 2
Input: ["TopVotedCandidate","q","q"]
[[[1,0],[7,8]],[7],[1000000000]]
Output: [null,1,0]
Explanation: Candidate 1 leads at time 7. At time 8 candidate 0 draws level and, having received the latest vote, leads from then on.
Constraints
1 <= persons.length <= 5000times.length == persons.length0 <= persons[i] < persons.length0 <= times[i] <= 10^9times is strictly increasingtimes[0] <= t <= 10^9At most 10^4 calls are made to q
Hints for Online Election
Hint 1
The leader only changes when a vote arrives, so there are at most n different answers — one per vote.
Hint 2
Walk the votes once in time order, keeping a count per candidate and the current leader. After vote
i, record who leads.Hint 3
A query at time
tasks about the last vote cast at or beforet: find it with a binary search overtimesand return the leader recorded there. Ties go to the newest voter, so update the leader when the new count is>=the leader's.
How to solve Online Election
Precompute the leader after every vote, then answer each query by binary searching for the last vote at or before t.
Approach
- Scan the votes in order with a count per candidate and a current
leader. - After counting vote
ifor candidatep, ifcount[p] >= count[leader]thenleader = p; storelead[i] = leader. q(t): binary search the largestiwithtimes[i] <= t(it exists becauset >= times[0]) and returnlead[i].
Why it works
Between two consecutive votes the counts do not change, so the leader at time t is the leader just after the last vote cast at or before t. During the scan only the candidate who just received a vote can overtake: with >=, a candidate who draws level becomes leader because they are now the most recent voter among the tied ones, which is exactly the tie rule.
Complexity
- Time —
O(n) to build, O(log n) per query - Space —
O(n)
Pitfalls
- Using
>instead of>=keeps the older candidate on a tie — the rule is the opposite. - A vote cast exactly at time
tcounts; search for the last time<= t, not< t. - Recounting the votes for every query is O(n) a query, 5 × 10^7 steps at the limits.
Reference solution
Python
import bisect
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
self.times = times
self.lead = []
count = [0] * len(persons)
leader = persons[0]
for p in persons:
count[p] += 1
if count[p] >= count[leader]: # a tie goes to the newest voter
leader = p
self.lead.append(leader)
def q(self, t: int) -> int:
return self.lead[bisect.bisect_right(self.times, t) - 1]Java
class TopVotedCandidate {
private int[] times, lead;
public TopVotedCandidate(int[] persons, int[] times) {
this.times = times;
lead = new int[persons.length];
int[] count = new int[persons.length];
int leader = persons[0];
for (int i = 0; i < persons.length; i++) {
int p = persons[i];
count[p]++;
if (count[p] >= count[leader]) leader = p; // a tie goes to the newest voter
lead[i] = leader;
}
}
public int q(int t) {
int lo = 0, hi = times.length - 1; // last vote at or before t
while (lo < hi) {
int mid = (lo + hi + 1) >>> 1;
if (times[mid] <= t) lo = mid; else hi = mid - 1;
}
return lead[lo];
}
}C++
class TopVotedCandidate {
vector<int> times, lead;
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
vector<int> count(persons.size(), 0);
int leader = persons[0];
for (int p : persons) {
count[p]++;
if (count[p] >= count[leader]) leader = p; // a tie goes to the newest voter
lead.push_back(leader);
}
}
int q(int t) {
int i = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
return lead[i];
}
};JavaScript
var TopVotedCandidate = function(persons, times) {
this.times = times;
this.lead = [];
var count = new Array(persons.length).fill(0);
var leader = persons[0];
for (var i = 0; i < persons.length; i++) {
var p = persons[i];
count[p]++;
if (count[p] >= count[leader]) leader = p; // a tie goes to the newest voter
this.lead.push(leader);
}
};
TopVotedCandidate.prototype.q = function(t) {
var lo = 0, hi = this.times.length - 1; // last vote at or before t
while (lo < hi) {
var mid = (lo + hi + 1) >> 1;
if (this.times[mid] <= t) lo = mid; else hi = mid - 1;
}
return this.lead[lo];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets