Online Election: Precompute Leaders and Binary Search

LeetCode 911, Online Election, is a medium problem that combines preprocessing with binary search. You are given a list of votes with timestamps, and you need to answer queries asking "who was winning at time t?" The key insight is to separate the work into two phases: an upfront preprocessing step that records the leader at every vote time, and a query step that uses binary search to find the right moment in time.

The problem

You are given two arrays: persons[i] is the candidate who received the i-th vote, and times[i] is the timestamp of that vote. Times are strictly increasing. A candidate is "leading" if they have the most votes at that point. In case of a tie, the candidate who received the most recent vote wins.

You need to implement a class with a method q(t) that returns the leader at time t. It is guaranteed that a vote exists at or before time t.

Input:  persons = [0, 1, 1, 0, 0, 1, 0], times = [0, 5, 10, 15, 20, 25, 30]
Query:  q(3) = 0, q(12) = 1, q(25) = 1, q(15) = 0, q(24) = 0, q(8) = 1

Why this problem matters

This problem teaches a powerful design pattern: precompute expensive answers during initialization so that queries become cheap. Instead of recounting votes on every query, you do the work once and store the result. Then each query is just a lookup with binary search.

This pattern appears frequently in system design and real-world applications. Think of leaderboard systems that snapshot rankings at intervals, or time-series databases that precompute aggregations. The combination of hash maps for counting and binary search for time-based queries is a versatile toolkit.

The problem also reinforces how to handle tie-breaking rules cleanly. The >= comparison in the code naturally gives precedence to the most recent voter in a tie, which matches the problem statement.

The brute force approach

The naive way is to recount all votes up to time t for every query:

class TopVotedCandidate:
    def __init__(self, persons, times):
        self.persons = persons
        self.times = times

    def q(self, t):
        counts = {}
        leader = -1
        for i, time in enumerate(self.times):
            if time > t:
                break
            p = self.persons[i]
            counts[p] = counts.get(p, 0) + 1
            if counts[p] >= counts.get(leader, 0):
                leader = p
        return leader

This works but each query scans up to n votes. If you have q queries, the total time is O(n * q), which is too slow when both n and q can be up to 5000.

The key insight

The leader can only change when a vote is cast. Between two consecutive vote times, the leader stays the same. This means you only need to know the leader at each of the n vote times. For any query time t, find the last vote time that is <= t, and return the leader at that moment.

The preprocessing is a single pass through the votes, maintaining a count dictionary and tracking the current leader. The query is a binary search on the sorted times array.

The solution

import bisect

class TopVotedCandidate:
    def __init__(self, persons, times):
        self.times = times
        self.leaders = []
        counts = {}
        leader = -1
        for p in persons:
            counts[p] = counts.get(p, 0) + 1
            if counts[p] >= counts.get(leader, 0):
                leader = p
            self.leaders.append(leader)

    def q(self, t):
        idx = bisect.bisect_right(self.times, t) - 1
        return self.leaders[idx]

Here is what each piece does:

1. self.times = times stores the vote timestamps for binary search during queries.
2. self.leaders = [] will hold the precomputed leader at each vote index.
3. The for loop processes each vote in order. It increments the vote count for person p, then checks if p is now the leader. The >= comparison means that in a tie, the most recent voter wins.
4. self.leaders.append(leader) records the leader after processing this vote.
5. bisect.bisect_right(self.times, t) - 1 finds the largest index where times[idx] <= t. This is the last vote that was cast at or before time t.
6. return self.leaders[idx] returns the precomputed leader at that index.

Walking through it step by step

Complexity analysis

The initialization processes all n votes in a single pass, which is O(n). Each query performs a binary search on the times array, which is O(log n). If you make q queries, the total query time is O(q log n). Combined, the total is O(n + q log n).

The space is O(n) for storing the times array and the leaders array. The counts dictionary uses at most O(n) space as well during preprocessing, though it could be discarded afterward since the leaders array captures all the information needed for queries.

Building blocks

1. Precomputed prefix answers

The core pattern is computing answers at each prefix so that later queries become lookups:

answers = []
state = initial_state
for item in data:
    state = update(state, item)
    answers.append(extract(state))

This is useful any time queries ask about "the state at some point in the sequence." Instead of replaying the sequence for each query, you precompute and store. The Online Election problem uses this with vote counts and a running leader.

2. Binary search on sorted keys

When you have precomputed answers at sorted positions (like timestamps), queries for arbitrary positions use binary search:

import bisect
idx = bisect.bisect_right(sorted_keys, query_key) - 1
return answers[idx]

bisect_right gives the insertion point where query_key would go to keep the list sorted. Subtracting 1 gives the last existing key that is <= the query key. This pattern works for any "find the most recent event before time t" query.

Edge cases

Before submitting, verify your solution handles:

• All votes for the same person like persons = [0, 0, 0]: the leader is always 0. Every query returns 0.
• Query at exact vote time: q(times[i]) should return leaders[i]. The bisect_right - 1 formula handles this correctly since bisect_right returns the index after the match.
• Query between two vote times: q(t) where times[i] < t < times[i+1] should return leaders[i]. Binary search naturally finds index i.
• Tie-breaking: when two candidates have equal votes, the one who received the most recent vote wins. The >= comparison ensures this.
• Single vote: one vote at time 0. Any query returns that person.
• Query at the last time: q(times[n-1]) should return the final leader.

Common mistakes

1. Using bisect_left instead of bisect_right. With bisect_left, a query at an exact vote time might land at that index instead of after it, which still works when you subtract 1. However, bisect_right is the standard approach and makes the intent clearer: find the first position after t, then step back one.

2. Using > instead of >= for the leader comparison. The problem states that in a tie, the most recent voter leads. Using > would not update the leader on a tie, giving the wrong answer.

3. Not storing leaders at all. Some people try to binary search to find the index and then recount votes up to that index. This defeats the purpose of preprocessing and makes queries O(n).

4. Off-by-one in binary search. Forgetting to subtract 1 from bisect_right gives you the index after the last valid vote, which may be out of bounds or point to a future vote.

From understanding to recall

You have walked through the Online Election algorithm in detail. The idea is clean: precompute the leader at each vote time using a running count, then answer queries with binary search on the times array. Two phases, two data structures, one clean solution.

The details that trip people up under pressure are subtle. Is the comparison >= or >? Do you use bisect_left or bisect_right? Do you subtract 1 or not? These small choices determine whether your solution passes or fails on edge cases with ties and exact timestamps.

Spaced repetition turns this from "I remember the general idea" into "I can write this in two minutes." By revisiting the precompute-and-search pattern at increasing intervals, you build reliable recall of both the structure and the details. When you see a variant, like a time-based key-value store or a snapshot array, the pattern clicks immediately.

Related posts

• Binary Search on LeetCode - A comprehensive guide to binary search patterns including bisect_left vs bisect_right
• Top K Frequent Elements - Another problem combining hash map counting with efficient lookups
• Find First and Last Position of Element in Sorted Array - Practice with bisect_left and bisect_right to find boundaries in sorted arrays

CodeBricks drills the precompute-and-binary-search pattern as a reusable building block. You practice the preprocessing loop and the bisect query separately, then combine them under timed conditions. When Online Election or its variants appear in an interview, you write the solution confidently without second-guessing the details.