Online Election
MediumUpdated: Aug 2, 2025
Practice on:
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 thepersonsandtimesarrays.int q(int t)Returns the number of the person that was leading the election at timetaccording to the mentioned rules.
Examples
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 <= 5000times.length == persons.length0 <= persons[i] < persons.length0 <= times[i] <= 10^9timesis sorted in a strictly increasing order.times[0] <= t <= 10^9- At most
104calls will be made toq.
Solution
Method 1 – Prefix Leader Array + Binary Search
Intuition
We want to answer queries for the leader at any time t efficiently. By precomputing the leader after each vote, we can use binary search to quickly find the leader at any query time.
Approach
- In the constructor, iterate through the votes, keep a count for each person, and track the current leader after each vote. Store the leader at each time.
- For each query, use binary search to find the last time <= t, and return the leader at that time.
Code
C++
class TopVotedCandidate {
vector<int> times, leaders;
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times_) {
unordered_map<int, int> cnt;
int lead = -1, mx = 0;
for (int i = 0; i < persons.size(); ++i) {
int p = persons[i];
cnt[p]++;
if (cnt[p] >= mx) {
mx = cnt[p];
lead = p;
}
leaders.push_back(lead);
}
times = times_;
}
int q(int t) {
int l = 0, r = times.size()-1;
while (l < r) {
int m = (l+r+1)/2;
if (times[m] <= t) l = m; else r = m-1;
}
return leaders[l];
}
};
Go
type TopVotedCandidate struct {
times []int
leaders []int
}
func Constructor(persons []int, times []int) TopVotedCandidate {
cnt := map[int]int{}
leaders := make([]int, len(persons))
lead, mx := -1, 0
for i, p := range persons {
cnt[p]++
if cnt[p] >= mx {
mx = cnt[p]
lead = p
}
leaders[i] = lead
}
return TopVotedCandidate{times, leaders}
}
func (this *TopVotedCandidate) Q(t int) int {
l, r := 0, len(this.times)-1
for l < r {
m := (l+r+1)/2
if this.times[m] <= t {
l = m
} else {
r = m-1
}
}
return this.leaders[l]
}
Java
class TopVotedCandidate {
int[] times, leaders;
public TopVotedCandidate(int[] persons, int[] times) {
this.times = times;
leaders = new int[persons.length];
Map<Integer, Integer> cnt = new HashMap<>();
int lead = -1, mx = 0;
for (int i = 0; i < persons.length; i++) {
int p = persons[i];
cnt.put(p, cnt.getOrDefault(p, 0) + 1);
if (cnt.get(p) >= mx) {
mx = cnt.get(p);
lead = p;
}
leaders[i] = lead;
}
}
public int q(int t) {
int l = 0, r = times.length-1;
while (l < r) {
int m = (l+r+1)/2;
if (times[m] <= t) l = m; else r = m-1;
}
return leaders[l];
}
}
Kotlin
class TopVotedCandidate(persons: IntArray, private val times: IntArray) {
private val leaders = IntArray(persons.size)
init {
val cnt = mutableMapOf<Int, Int>()
var lead = -1; var mx = 0
for (i in persons.indices) {
val p = persons[i]
cnt[p] = cnt.getOrDefault(p, 0) + 1
if (cnt[p]!! >= mx) {
mx = cnt[p]!!
lead = p
}
leaders[i] = lead
}
}
fun q(t: Int): Int {
var l = 0; var r = times.size-1
while (l < r) {
val m = (l+r+1)/2
if (times[m] <= t) l = m else r = m-1
}
return leaders[l]
}
}
Python
class TopVotedCandidate:
def __init__(self, persons: list[int], times: list[int]):
self.times = times
self.leaders = []
cnt: dict[int, int] = {}
lead = -1
mx = 0
for p in persons:
cnt[p] = cnt.get(p, 0) + 1
if cnt[p] >= mx:
mx = cnt[p]
lead = p
self.leaders.append(lead)
def q(self, t: int) -> int:
l, r = 0, len(self.times) - 1
while l < r:
m = (l + r + 1) // 2
if self.times[m] <= t:
l = m
else:
r = m - 1
return self.leaders[l]
Rust
struct TopVotedCandidate {
times: Vec<i32>,
leaders: Vec<i32>,
}
impl TopVotedCandidate {
fn new(persons: Vec<i32>, times: Vec<i32>) -> Self {
let mut cnt = std::collections::HashMap::new();
let mut leaders = Vec::with_capacity(persons.len());
let mut lead = -1;
let mut mx = 0;
for &p in &persons {
*cnt.entry(p).or_insert(0) += 1;
if cnt[&p] >= mx {
mx = cnt[&p];
lead = p;
}
leaders.push(lead);
}
Self { times, leaders }
}
fn q(&self, t: i32) -> i32 {
let (mut l, mut r) = (0, self.times.len()-1);
while l < r {
let m = (l+r+1)/2;
if self.times[m] <= t { l = m; } else { r = m-1; }
}
self.leaders[l]
}
}
TypeScript
class TopVotedCandidate {
private times: number[]
private leaders: number[]
constructor(persons: number[], times: number[]) {
this.times = times
this.leaders = []
const cnt = new Map<number, number>()
let lead = -1, mx = 0
for (let p of persons) {
cnt.set(p, (cnt.get(p) ?? 0) + 1)
if (cnt.get(p)! >= mx) {
mx = cnt.get(p)!
lead = p
}
this.leaders.push(lead)
}
}
q(t: number): number {
let l = 0, r = this.times.length - 1
while (l < r) {
let m = (l + r + 1) >> 1
if (this.times[m] <= t) l = m
else r = m - 1
}
return this.leaders[l]
}
}
Complexity
- ⏰ Time complexity:
O(log n)per query,O(n)for preprocessing, where n is the number of votes. - 🧺 Space complexity:
O(n), for storing leaders and times.