LeetCode Solutions Blog

Online Election

Number: 947

Difficulty: Medium

Paid? No

Problem Description

You are given two integer arrays persons and times. The i-th vote was cast for persons[i] at time times[i]. For each query at a time t, determine the person who was leading the election at time t. Votes cast at time t count towards the query, and in the case of a tie, the most recent vote wins.

Key Insights

Precompute the leader at each vote time.
Use a hash table to count votes per candidate while iterating through the persons array.
Maintain a leaders list that records the current leader at each corresponding vote time.
Use binary search on the times array to efficiently answer queries for any time t.

Space and Time Complexity

Time Complexity: O(n + q log n), where n is the number of votes and q is the number of queries. Space Complexity: O(n), to store the leaders for each vote and the counts for each candidate.

Solution

We process the vote records sequentially, tracking vote counts in a hash table and updating the current leader when a candidate's vote count is equal to or exceeds that of the current leader. This leader is saved along with each vote time. For each query, binary search is used on the times array to find the last vote time that is less than or equal to the query time, and the leader corresponding to that time is returned.

Code Solutions

class TopVotedCandidate:
    def __init__(self, persons, times):
        # Precompute the leader for each vote timestamp.
        self.leaders = []
        self.counts = {}
        current_leader = None
        
        # Process each vote.
        for person in persons:
            self.counts[person] = self.counts.get(person, 0) + 1
            # Update leader in case of tie or increased vote count.
            if current_leader is None or self.counts[person] >= self.counts.get(current_leader, 0):
                current_leader = person
            self.leaders.append(current_leader)
        
        # Store the vote times for binary search.
        self.times = times

    def q(self, t):
        # Binary search for the index of the largest time <= t.
        low, high = 0, len(self.times) - 1
        while low <= high:
            mid = (low + high) // 2
            if self.times[mid] <= t:
                low = mid + 1
            else:
                high = mid - 1
        return self.leaders[high] if high >= 0 else None

# Example usage:
# persons = [0, 1, 1, 0, 0, 1, 0]
# times = [0, 5, 10, 15, 20, 25, 30]
# topVotedCandidate = TopVotedCandidate(persons, times)
# print(topVotedCandidate.q(3))  # Output: 0