Problem 911

Abstract / Summary

Track votes for candidates and return the leading candidate with the most votes at any time.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0911.py

class TopVotedCandidate:
    def __init__(self, persons: List[int], times: List[int]):
        self.leader = defaultdict(int)
        self.times  = times

        candidates = max(persons) + 1

        # current leader
        best  = 0
        votes = [ 0 ] * candidates
        for p, t in zip(persons, times):
            # add a vote
            votes[p] += 1
            # new leader (tie => most recent)
            if votes[best] <= votes[p]:
                best = p
            self.leader[t] = best

    def q(self, t: int) -> int:
        pos  = bisect_right(self.times, t) - 1
        when = self.times[pos]
        return self.leader[when]
22 lines | 675 bytes | submitted November 23, 2023 | GitHub   18% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 53% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Binary Search
  • Design
  • Hash Table
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The class implements a data structure that, given a chronological list of votes, can answer “who was leading at time t?” queries efficiently. The constructor builds an internal map from each voting timestamp to the candidate who was in the lead immediately after that vote. The query method uses binary search to locate the most recent timestamp not greater than the requested time and returns the stored leader.

Construction Process

The constructor receives two parallel arrays: persons (the candidate receiving each vote) and times (the moment the vote was cast).

def __init__(self, persons: List[int], times: List[int]):
    self.leader = defaultdict(int)
    self.times  = times

A dictionary leader is prepared to associate each timestamp with the current leader. The original list of timestamps is stored unchanged for later binary search.

The number of distinct candidate identifiers is inferred from the maximum value in persons.

candidates = max(persons) + 1

An integer list votes of that length is allocated, all entries starting at zero, to count how many votes each candidate has received so far.

votes = [0] * candidates

A variable best holds the identifier of the candidate who is currently leading. It is initialized to zero, which also serves as a default leader before any votes are processed.

best = 0

The core loop iterates over the paired elements of persons and times. For each vote the corresponding entry in votes is incremented.

for p, t in zip(persons, times):
    votes[p] += 1

After updating the vote count, the algorithm determines whether the newly voted candidate overtakes the current leader. The comparison uses <= so that a tie is resolved in favor of the most recent vote, thereby updating best to the candidate that just received a vote when their total equals the leader’s total.

    if votes[best] <= votes[p]:
        best = p

Finally, the mapping from the current timestamp to the leader after processing that vote is recorded.

    self.leader[t] = best

When the loop finishes, self.leader contains a complete chronological record of the leader at each voting moment, and self.times retains the ordered timestamps.

Query Operation

The q method answers a query for any time t. It first finds the index of the greatest timestamp that does not exceed t. This is achieved with bisect_right, which returns the insertion point for t in the sorted times list; subtracting one yields the index of the relevant timestamp.

pos = bisect_right(self.times, t) - 1

The timestamp at that position is retrieved, and the pre-computed leader for that moment is returned from the dictionary.

when = self.times[pos]
return self.leader[when]

Because the timestamps are stored in order, the binary search runs in logarithmic time, providing fast responses even for large histories.

Edge Cases Handled

When a query time precedes the first vote, bisect_right returns zero, and after subtracting one the index becomes -1. In Python negative indexing wraps to the last element, but because the timestamps are strictly increasing and the problem guarantees that queries will be within the range of recorded times, this situation does not arise in normal usage.

If multiple candidates have the same vote count after a vote, the <= comparison ensures that the candidate who just received the vote becomes the leader. This rule matches the “most recent” tie-breaking policy.

When the query time is later than the last recorded vote, bisect_right yields a position equal to the length of times. Subtracting one yields the index of the final timestamp, and the method correctly returns the leader after the last vote.

The constructor also gracefully handles the case where the candidate identifiers are not contiguous. By allocating the votes list based on the maximum identifier plus one, any gaps are represented by unused slots that remain at zero, and the algorithm still updates counts correctly for the actual identifiers that appear.

Performance Optimizations

The implementation pre-computes the leader for every voting instant during construction, turning each query into a simple dictionary lookup after a binary search. This avoids recomputing vote tallies on the fly.

Using a plain Python list for votes provides O(1) access and update for each candidate’s count, which is faster than a dictionary when the identifier space is dense.

The choice of defaultdict(int) for leader eliminates the need to check for missing keys when inserting entries, streamlining the loop body.

Binary search via bisect_right leverages the underlying C implementation in the standard library, delivering fast logarithmic lookups without manual loop code.

Overall, the design balances one-time linear work during initialization with sub-linear query time, making it well-suited for scenarios with many queries after a relatively static voting history.

written by openai gpt

ELI5 - Simplified Explanation

Imagine holding an election where all the people cast their votes one after another. This code acts like a very smart recorder that watches the whole process to keep track of who is winning at every single moment.

Inside the first part, the computer creates a list to count how many votes each person gets. As the votes come in, the computer checks if the person who just got a vote has more than the person currently leading. If there is a tie or a new winner, the computer marks that person as the new leader for that specific time. It remembers these records in a special book so it does not have to guess later.

When someone asks who was leading at a certain time, the second part of the code looks through the history of when votes happened. It finds the closest time before or during the moment requested and looks up the leader that was written down for that exact time in the special book.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.52 | σ = 0.83

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
fengvyi C++
fsq C++
halfrost Go
JoshCrozier JS
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
fengvyi C++
fsq C++
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
YuriSpiridonov Python
zfang399 C++
33 links | 20 authors | 9 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

15 solutions   November 23, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality