Problem Description

You are given information about an election where votes are cast at different times. The election data consists of two arrays:

• persons[i] represents that the i-th vote was cast for candidate persons[i]
• times[i] represents the time when the i-th vote was cast

Your task is to implement a system that can answer queries about who was leading the election at any given time t. When querying for time t, all votes cast at or before time t should be counted.

The rules for determining the leader are:

• The candidate with the most votes is the leader
• In case of a tie (multiple candidates have the same highest vote count), the candidate who most recently received a vote wins

You need to implement a TopVotedCandidate class with:

• A constructor TopVotedCandidate(int[] persons, int[] times) that initializes the election data
• A method q(int t) that returns the candidate number who was leading at time t

For example, if persons = [0, 1, 1, 0, 0, 1, 0] and times = [0, 5, 10, 15, 20, 25, 30]:

• At time 5: candidate 0 has 1 vote, candidate 1 has 1 vote (tie, but 1 voted more recently, so 1 leads)
• At time 15: candidate 0 has 2 votes, candidate 1 has 2 votes (tie, but 0 voted more recently at time 15, so 0 leads)
• At time 30: candidate 0 has 4 votes, candidate 1 has 3 votes (0 leads with more votes)

The solution precomputes the leader at each voting time during initialization, then uses binary search to efficiently answer queries by finding the appropriate time point.

Intuition

The key insight is that the election leader only changes when a new vote is cast. Between any two consecutive votes, the leader remains the same. This means we don't need to calculate the winner for every possible time value - we only need to know who was winning after each vote was counted.

Think about it this way: if we're asked "who was leading at time 17?", and votes were cast at times [0, 5, 10, 15, 20, 25, 30], we need to count all votes up to and including time 15 (since 17 is between 15 and 20). The winner at time 17 is the same as the winner right after the vote at time 15 was counted.

This observation leads us to a two-phase approach:

Phase 1 (Preprocessing): When we initialize the system, we can simulate the entire election chronologically. For each vote cast, we:

• Update the vote count for that candidate
• Check if this changes the current leader (either they now have more votes, or they tie with the current leader and become the new leader due to the tie-breaking rule)
• Record who is leading after this vote

Phase 2 (Query): When asked about time t, we need to find which votes had been cast by that time. Since the times array is sorted, we can use binary search to find the last vote that occurred at or before time t. The leader at that point in the election is our answer.

The binary search specifically looks for the rightmost position where times[i] <= t. This gives us the index of the last vote that should be counted for our query. We can then directly return the precomputed winner at that index.

This approach transforms a potentially expensive query (counting all votes up to time t for each query) into a simple binary search and array lookup, making each query O(log n) instead of O(n).

Learn more about Binary Search patterns.

Solution Approach

The implementation consists of two main components: initialization and query handling.

Initialization (__init__ method):

1. Data Structures Setup:

   • cnt = Counter(): A counter dictionary to track the vote count for each candidate
   • self.times = times: Store the times array for later binary search
   • self.wins = []: An array to store the winner after each vote
   • cur = 0: Variable to track the current leading candidate

2. Processing Each Vote:

   • For each person in the persons array:
     • cnt[p] += 1: Increment the vote count for candidate p
     • if cnt[cur] <= cnt[p]: Check if the current vote changes the leader
       • If candidate p now has more votes than the current leader, they become the new leader
       • If candidate p ties with the current leader, they also become the new leader (tie-breaking rule: most recent vote wins)
     • cur = p: Update the current leader if necessary
     • self.wins.append(cur): Record who is leading after this vote

   The condition cnt[cur] <= cnt[p] is crucial - it handles both cases:

   • When p has strictly more votes (cnt[cur] < cnt[p])
   • When p ties with the current leader (cnt[cur] == cnt[p]), making p the new leader due to being the most recent

Query Method (q method):

1. Binary Search:

   • bisect_right(self.times, t): Finds the insertion point for t in the sorted times array
   • This returns the index where t would be inserted to maintain sorted order
   • Subtracting 1 (- 1) gives us the index of the last vote that occurred at or before time t

2. Return Winner:

   • return self.wins[i]: Return the precomputed winner at index i

Example Walkthrough:

If persons = [0, 1, 1, 0] and times = [5, 10, 15, 20]:

• After vote at time 5: candidate 0 has 1 vote, leads → wins[0] = 0
• After vote at time 10: candidate 1 has 1 vote, ties but voted more recently → wins[1] = 1
• After vote at time 15: candidate 1 has 2 votes, leads → wins[2] = 1
• After vote at time 20: candidate 0 has 2 votes, ties but voted more recently → wins[3] = 0

For query q(12):

• bisect_right([5, 10, 15, 20], 12) returns 2
• Index 2 - 1 = 1
• Return wins[1] = 1

Time Complexity:

• Initialization: O(n) where n is the number of votes
• Query: O(log n) due to binary search

Space Complexity: O(n) to store the wins array and vote counts

Example Walkthrough

Let's walk through a small example with persons = [0, 1, 0, 1, 1] and times = [2, 4, 6, 8, 10].

Initialization Phase - Building the wins array:

Starting with cnt = {}, cur = 0, wins = []

1. Time 2, Vote for candidate 0:

   • cnt = {0: 1}, candidate 0 has 1 vote
   • Check: cnt[0] (0) <= cnt[0] (1)? Yes, so cur = 0
   • wins = [0] (candidate 0 leads)

2. Time 4, Vote for candidate 1:

   • cnt = {0: 1, 1: 1}, candidate 1 has 1 vote
   • Check: cnt[0] (1) <= cnt[1] (1)? Yes (tie), so cur = 1 (candidate 1 wins tie)
   • wins = [0, 1] (candidate 1 now leads)

3. Time 6, Vote for candidate 0:

   • cnt = {0: 2, 1: 1}, candidate 0 has 2 votes
   • Check: cnt[1] (1) <= cnt[0] (2)? Yes, so cur = 0
   • wins = [0, 1, 0] (candidate 0 leads)

4. Time 8, Vote for candidate 1:

   • cnt = {0: 2, 1: 2}, candidate 1 has 2 votes
   • Check: cnt[0] (2) <= cnt[1] (2)? Yes (tie), so cur = 1 (candidate 1 wins tie)
   • wins = [0, 1, 0, 1] (candidate 1 leads)

5. Time 10, Vote for candidate 1:

   • cnt = {0: 2, 1: 3}, candidate 1 has 3 votes
   • Check: cnt[1] (3) <= cnt[1] (3)? Yes, cur stays 1
   • wins = [0, 1, 0, 1, 1] (candidate 1 leads)

Final state: times = [2, 4, 6, 8, 10], wins = [0, 1, 0, 1, 1]

Query Phase - Answering queries:

Query q(3):

• Binary search: bisect_right([2, 4, 6, 8, 10], 3) returns 1
• Index: 1 - 1 = 0
• Return: wins[0] = 0
• Meaning: At time 3, only the vote at time 2 has been cast, so candidate 0 leads

Query q(7):

• Binary search: bisect_right([2, 4, 6, 8, 10], 7) returns 3
• Index: 3 - 1 = 2
• Return: wins[2] = 0
• Meaning: At time 7, votes at times 2, 4, and 6 have been cast, candidate 0 leads with 2 votes

Query q(10):

• Binary search: bisect_right([2, 4, 6, 8, 10], 10) returns 5
• Index: 5 - 1 = 4
• Return: wins[4] = 1
• Meaning: At time 10, all votes have been cast, candidate 1 leads with 3 votes

The key insight is that we precompute the leader after each vote during initialization, then use binary search to quickly find which leader to return for any given time query.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(n), where n is the length of the persons and times arrays. The constructor iterates through all n persons exactly once, and for each person, it performs constant-time operations (updating the counter, comparison, and appending to the wins list).

• Query (q): O(log n), where n is the length of the times array. The bisect_right function performs a binary search on the sorted times array to find the appropriate position, which takes logarithmic time. After finding the index, accessing the element in self.wins is O(1).

Space Complexity:

• O(n), where n is the length of the input arrays. The space is used to store:

  • self.times: stores a reference to the input times array (or a copy of it), which is O(n)
  • self.wins: stores the winning candidate at each time point, which is O(n)
  • cnt (Counter): in the worst case stores up to n unique persons, which is O(n)

  The total space complexity is therefore O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Tie-Breaking Logic

Pitfall: A common mistake is using strict inequality (<) instead of less-than-or-equal (<=) when checking if a candidate should become the new leader:

# WRONG - This doesn't handle ties correctly
if vote_counter[current_leader] < vote_counter[person]:
    current_leader = person

This fails because when there's a tie, the most recent voter should win, but strict inequality won't update the leader.

Solution: Always use <= to ensure ties are broken in favor of the most recent voter:

# CORRECT - Handles both cases: more votes OR tied votes
if vote_counter[current_leader] <= vote_counter[person]:
    current_leader = person

2. Off-by-One Error in Binary Search

Pitfall: Using bisect_left instead of bisect_right, or forgetting to subtract 1:

# WRONG - bisect_left might give incorrect results for exact matches
index = bisect.bisect_left(self.times, t)

# WRONG - forgetting to subtract 1
index = bisect.bisect_right(self.times, t)

Solution: Use bisect_right and subtract 1 to get the last vote at or before time t:

# CORRECT
index = bisect.bisect_right(self.times, t) - 1

3. Not Handling Edge Cases

Pitfall: Not considering queries for times before the first vote:

def q(self, t: int) -> int:
    index = bisect.bisect_right(self.times, t) - 1
    # If t < times[0], index becomes -1, causing incorrect array access
    return self.leading_candidates[index]

Solution: Add validation or ensure the problem constraints guarantee valid queries:

def q(self, t: int) -> int:
    index = bisect.bisect_right(self.times, t) - 1
    # Ensure index is valid (though usually guaranteed by problem constraints)
    if index < 0:
        return -1  # or handle according to requirements
    return self.leading_candidates[index]

4. Inefficient Query Implementation

Pitfall: Recalculating the leader for each query instead of precomputing:

# WRONG - O(n) per query
def q(self, t: int) -> int:
    vote_count = Counter()
    leader = -1
    for i in range(len(self.times)):
        if self.times[i] <= t:
            vote_count[self.persons[i]] += 1
            # Recalculate leader...
    return leader

Solution: Precompute leaders during initialization and use binary search for O(log n) queries.