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]
Difficulty
and has an acceptance rate of about 53% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Binary Search
- Design
- Hash Table
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 1366: Rank Teams by Votes
Solved On The Same Day
- problem 2932: Maximum Strong Pair XOR I
- problem 731: My Calendar II
- problem 792: Number of Matching Subsequences
- problem 820: Short Encoding of Words
- problem 950: Reveal Cards In Increasing Order
- problem 1023: Camelcase Matching
- problem 1038: Binary Search Tree to Greater Sum Tree
- problem 1170: Compare Strings by Frequency of the Smallest Character
- problem 1171: Remove Zero Sum Consecutive Nodes from Linked List
- problem 1696: Jump Game VI
- problem 2327: Number of People Aware of a Secret
- problem 432: All O`one Data Structure
- problem 732: My Calendar III
- problem 1044: Longest Duplicate Substring
Extra
- 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