Online Election - Solution & Explanation

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.