We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Online Election

Difficulty: Medium

Problem Description

You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i]. For each query at a time t, find the person that was leading the election at time t. Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Key Insights

  • Each vote is associated with a specific time, and votes are given in chronological order.
  • The leader can change over time based on the votes, and we must determine the leader at multiple query times.
  • A hash table can be used to keep track of the vote counts and determine the leader efficiently.
  • Binary search can be utilized to quickly find the latest time less than or equal to the query time.

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), for storing the counts of votes.

Solution

To solve this problem, we can maintain an array that records the leading candidate at each voting time. We iterate through the persons and times arrays to count votes for each candidate using a hash table. After updating the vote counts, we keep track of the current leading candidate and store it in an array. For each query, we use binary search on the times array to find the appropriate index and return the leading candidate at that time.

Code Solutions

class TopVotedCandidate:
    def __init__(self, persons: List[int], times: List[int]):
        self.times = times
        self.winner_at_time = []
        vote_count = {}
        current_winner = -1
        max_votes = 0
        
        for person in persons:
            # Count the votes for the current person
            vote_count[person] = vote_count.get(person, 0) + 1
            
            # Determine the current winner
            if vote_count[person] >= max_votes:
                max_votes = vote_count[person]
                current_winner = person
            
            # Record the current winner at the current time
            self.winner_at_time.append(current_winner)

    def q(self, t: int) -> int:
        # Binary search to find the latest time <= t
        left, right = 0, len(self.times) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if self.times[mid] <= t:
                left = mid
            else:
                right = mid - 1
        return self.winner_at_time[left]
← Back to All Questions