Skip to main content
Talentd

Online Election - Solution & Explanation

MediumArrayHash TableBinary SearchDesign13 min readAsked at: Google, Flipkart, Bloomberg
Practice this problem

Problem Statement

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 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] <= 109
  • times is sorted in a strictly increasing order.
  • times[0] <= t <= 109
  • At most 104 calls will be made to q.

Approach Overview

Problem Overview: You receive two arrays: persons and times. Each vote is cast for persons[i] at time times[i]. After preprocessing the votes, you must answer queries q(t) that return the candidate leading at time t. If multiple candidates tie, the most recent vote wins.

Approach 1: Vote Counting with On-Demand Search (O(n) per query time, O(n) space)

For each query, first locate the last vote that occurred at or before time t. Since times is sorted, use binary search to find this index in O(log n). Then iterate from index 0 to that position and count votes using a hash map. Track the candidate with the highest frequency and apply the tie‑breaking rule by preferring the most recent vote. This approach uses hash tables for counting and binary search for locating the relevant vote window.

The downside is repeated work. Every query recomputes vote counts from scratch, giving O(n) processing per query and O(n) extra space for the frequency map. It works when the number of queries is small or when simplicity matters more than query performance.

Approach 2: Precomputation Using Binary Search (O(n) preprocessing, O(log n) per query, O(n) space)

Instead of recomputing results for every query, compute the leader after each vote during initialization. Iterate once through persons, maintain a frequency map of votes, and track the current leader. Whenever a candidate’s vote count becomes greater than or equal to the current leader’s count, update the leader (this naturally handles the tie-breaking rule because the later vote wins). Store the leader at each index in a separate array.

When a query q(t) arrives, use binary search on the times array to find the last vote that occurred before or at t. The answer is simply the precomputed leader stored at that index. Query time becomes O(log n) and no recounting is required. This design combines prefix-style preprocessing with efficient lookups and fits well with problems involving historical state queries.

The technique relies on arrays for storing prefix leaders, hash tables for vote counts, and binary search for fast time lookup. Conceptually, this also falls under design problems because the class must support efficient repeated queries.

Recommended for interviews: The precomputation approach is what interviewers expect. It demonstrates that you recognize repeated queries and move expensive work to preprocessing. The on-demand counting approach shows baseline understanding, but the binary-search + prefix leader design shows stronger algorithmic thinking and system design awareness.

Approach 1: Vote Counting with On-Demand Search

This approach involves maintaining a running tally of votes for each candidate as votes are cast over time. We store the leader at each time point to quickly answer queries by iterating through the recorded times to find the leader for a queried time.

The Python implementation maintains a dictionary to count votes for each person and updates the current leader whenever a person receives votes equal to or greater than the current leader’s votes. The leader at each time point is recorded. During a query, binary search is used to efficiently find the greatest time less than or equal to the queried time, and the leader at that time is returned.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(log n) per query due to binary search.

Space Complexity: O(n) for storing leaders and votes count.

Try this approach in the editor →

Approach 2: Precomputation Using Binary Search

This approach uses precomputation to store the leader at each vote time, allowing for fast retrieval using a binary search on the times array during query operations.

In the C++ implementation, an unordered map is used to maintain the counts of votes per candidate. As each vote is processed, the current leader is determined and stored in a vector. Queries utilize binary search to find the most appropriate time index to retrieve the leader.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(log n) per query using binary search.

Space Complexity: O(n) to store leaders and counts.

Try this approach in the editor →

Approach 3: Binary Search

We can record the winner at each moment during initialization, and then use binary search to find the largest moment less than or equal to t during the query, and return the winner at that moment.

During initialization, we use a counter cnt to record the votes of each candidate, and a variable cur to record the current leading candidate. Then we traverse each moment, update cnt and cur, and record the winner at each moment.

During the query, we use binary search to find the largest moment less than or equal to t, and return the winner at that moment.

In terms of time complexity, during initialization, we need O(n) time, and during the query, we need O(log n) time. The space complexity is O(n).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Vote Counting with On-Demand Search

Time Complexity: O(log n) per query due to binary search.

Space Complexity: O(n) for storing leaders and votes count.

Precomputation Using Binary Search

Time Complexity: O(log n) per query using binary search.

Space Complexity: O(n) to store leaders and counts.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Vote Counting with On-Demand SearchO(n) per queryO(n)When queries are few and implementation simplicity is preferred
Precomputation Using Binary SearchO(n) build + O(log n) per queryO(n)Best for many queries; avoids recomputing vote counts

Video Solution

LeetCode 911. Online Election • Happy Coding • 2,738 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Online Election easy or hard?
Online Election is rated Medium difficulty. The tricky part is recognizing that queries repeat over the same vote history, so recomputing counts each time is inefficient. Precomputing the leader timeline and using binary search reduces query time significantly.
Online Election Python/Java solution
Python implementations typically store leaders in a list and use the bisect module for binary search. Java solutions often use arrays with Arrays.binarySearch or manual binary search logic. Both follow the same idea: preprocess leaders in O(n) and answer queries in O(log n).
How to solve Online Election in O(n)?
Build a prefix leader array during initialization. Iterate through the votes once, maintain a hash map of vote counts, and update the current leader whenever a candidate reaches or ties the highest count. Store that leader for each vote index. Queries then only require binary search to map time t to the correct index.
What is the best approach for Online Election?
The most efficient solution precomputes the leading candidate after every vote and stores it in an array. Each query then performs a binary search on the times array to find the last vote before time t and returns the stored leader. This gives O(n) preprocessing and O(log n) query time, which scales well when many queries are executed.
Is Online Election asked at Google/Amazon/Meta?
Online Election is commonly associated with companies that emphasize system design and data structure problems, including Amazon and Google. The problem tests efficient query handling, preprocessing strategies, and binary search over time-based data.
What data structure is used in Online Election?
The typical solution uses arrays to store vote times and prefix leaders, a hash map to track vote counts per candidate, and binary search to locate the correct vote index for each query time. Together they allow fast updates and efficient historical queries.
What is the time complexity of Online Election?
Using the optimal design, preprocessing takes O(n) time to count votes and record the leader after each vote. Each query runs in O(log n) time because it uses binary search on the sorted times array. Space complexity is O(n) for storing vote counts and leader history.

Ready to solve this problem?

Practice Online Election with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rank Teams by Votes