Online Election — Precompute Leader Array + Binary Search [LC 911, Google]

Problem Statement#

In an election, voters cast votes at times times[i] for person persons[i]. Implement a class that answers: at time t, who is currently leading? (In a tie, the most recent vote-getter wins.)

Constraints:

• 1 <= persons.length <= 5000
• 0 <= persons[i] < persons.length
• times is strictly increasing
• 0 <= times[i] <= 10^9
• times[0] <= t <= 10^9
• At most 10^4 calls to q(t)

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]

Why This Problem Matters#

LC 911 is a system design + binary search problem asked by Google and Amazon. It tests two skills simultaneously: precomputing state to answer queries efficiently, and recognising that binary search applies to the precomputed array.

The naive approach — replaying all votes before time t for each query — is O(n) per query and O(n * q) total. With up to 10^4 queries over up to 5000 votes, that is 5 * 10^7 operations — borderline acceptable but not optimal. The precompute-then-query approach does O(n) preprocessing and O(log n) per query.

This precompute pattern appears in many interview problems: range minimum queries, static LRU caches, and any "answer repeated queries on fixed data" scenario.

The Core Insight#

Precompute: Scan through all votes chronologically. Track vote frequency for each person. At each vote, update the current leader (the new vote-getter becomes leader if they tie or exceed the current leader's count). Store the leader at each time step in a leaders array.

Query: Given time t, find the last vote event at or before t. This is a right-boundary binary search on times: find the largest index i where times[i] <= t, then return leaders[i].

The right-boundary search converges to the last event at or before t. Since times is strictly increasing, bisect_right(times, t) - 1 gives this index directly.

Visual Dry Run#

persons = [0,1,1,0,0,1,0], times = [0,5,10,15,20,25,30]

leaders = [0, 1, 1, 0, 0, 1, 0]

q(3): bisect_right([0,5,10,15,20,25,30], 3) = 1, leaders[1-1] = leaders[0] = 0. q(25): bisect_right(times, 25) = 6, leaders[5] = 1.

Solution (Optimal)#

from collections import defaultdict
import bisect
 
class TopVotedCandidate:
    def __init__(self, persons: list[int], times: list[int]):
        self.times = times
        self.leaders = []
        freq = defaultdict(int)
        leader = -1
 
        for person in persons:
            freq[person] += 1
            # Tie goes to the most recent vote-getter
            if leader == -1 or freq[person] >= freq[leader]:
                leader = person
            self.leaders.append(leader)
 
    def q(self, t: int) -> int:
        # Right-boundary search: find last index where times[i] <= t
        idx = bisect.bisect_right(self.times, t) - 1
        return self.leaders[idx]

class TopVotedCandidate {
    constructor(persons, times) {
        this.times = times;
        this.leaders = [];
        const freq = new Map();
        let leader = -1;
 
        for (const person of persons) {
            freq.set(person, (freq.get(person) || 0) + 1);
            // Most recent vote breaks ties
            if (leader === -1 || freq.get(person) >= freq.get(leader)) {
                leader = person;
            }
            this.leaders.push(leader);
        }
    }
 
    q(t) {
        // Right-boundary binary search: last times[i] <= t
        let lo = 0, hi = this.times.length - 1;
        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo + 1) / 2); // upper-mid for right boundary
            if (this.times[mid] <= t) lo = mid;
            else hi = mid - 1;
        }
        return this.leaders[lo];
    }
}

Time: Constructor O(n), each query O(log n) Space: O(n) for leaders and times arrays

Common Mistakes#

• Using bisect_left instead of bisect_right — bisect_left finds the first index >= t, not the last index <= t. You need bisect_right(times, t) - 1.
• Not handling ties correctly: "most recent vote-getter wins" means >= not > in the leader update condition.
• Forgetting the -1 after bisect_right — bisect_right gives the insertion point (one past the last <= t), so subtract 1.
• In the manual binary search: using lower-mid ((lo+hi)//2) with lo = mid causes infinite loops — use upper-mid when setting lo = mid.

Interview Tips#

• Separate the two phases cleanly in your explanation: "first, precompute the leader at each vote; second, binary search the times array per query."
• The tie-breaking rule ("most recent vote-getter wins") is easy to miss — mention it explicitly when explaining the precompute step.
• Use bisect_right and explain why bisect_left is wrong — this shows you understand both boundary variants.
• Mention the time/space trade-off: the O(n) space for leaders buys O(log n) per query vs O(n) per query without precomputation.

Follow-up Questions#

• What if queries can be at times before any vote? The problem guarantees times[0] <= t, so this cannot happen. If it could, return a default (no leader yet).
• What if the election is ongoing (new votes arrive)? The precomputed approach does not work for dynamic data. Use a sorted structure (e.g., SortedList) and recompute the leader on each new vote.
• LC 981 (Time Based Key-Value Store): Same precompute-then-binary-search pattern for key-value lookups at specific timestamps.
• Can you answer queries in O(1)? Only if you precompute answers for every possible time value — impossible since times can be up to 10^9. O(log n) per query is optimal.

Key Takeaways#

• LC 911 follows the precompute-then-query pattern: O(n) precomputation makes each query O(log n) instead of O(n).
• Precompute leaders[i] = the leading candidate just after vote i using a running frequency map and the tie-breaking rule.
• Query using right-boundary binary search on times: find the last index i where times[i] <= t, then return leaders[i].
• Use bisect_right(times, t) - 1 (not bisect_left) — bisect_right gives the first insertion point after all t, so subtract 1 to get the last event at or before t.
• The tie-breaking rule ("most recent vote wins") means the leader update uses >= not > — missing this gives wrong answers on tied votes.
• In the manual JavaScript binary search: use upper-mid lo + Math.floor((hi - lo + 1) / 2) with lo = mid to implement the right-boundary search correctly.
• This precompute-and-binary-search pattern generalises to LC 981 (Time Based KV Store) and any "answer queries at specific timestamps on historical data" problem.