Online Election

Medium

Asked by:

22 views

Topics:

ArraysBinary Search

You are given two integer arrays persons and times. In an election, the i^th 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.

Implement the TopVotedCandidate class:

TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
int q(int t) Returns the number of the person that was leading the election at time t according to the mentioned rules.

Example 1:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

Explanation
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // return 0, At time 3, the votes are [0], and 0 is leading.
topVotedCandidate.q(12); // return 1, At time 12, the votes are [0,1,1], and 1 is leading.
topVotedCandidate.q(25); // return 1, At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
topVotedCandidate.q(15); // return 0
topVotedCandidate.q(24); // return 0
topVotedCandidate.q(8); // return 1

Constraints:

1 <= persons.length <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 10⁹
times is sorted in a strictly increasing order.
times[0] <= t <= 10⁹
At most 10⁴ calls will be made to q.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you provide more details on the constraints for the `times` and `persons` arrays, such as their maximum length and the range of values they can contain?
Are the `times` array guaranteed to be strictly increasing? What happens if there are duplicate timestamps?
If multiple people have the same number of votes at a given time, which person is considered the leader?
What should be returned if I query for a time before the first entry in the `times` array?
Is it possible for the `persons` array to contain negative values, or are they always non-negative integers?

Brute Force Solution

Approach

The brute force approach involves recomputing the winner for every single query. Essentially, we go back to the original election results each time we're asked who's winning at a specific time. It's like recounting the votes from scratch every time someone asks for the current leader.

Here's how the algorithm would work step-by-step:

When someone asks who is winning at a certain time, look through all the votes that happened up to that time.
Count how many votes each person received up to that specific time.
The person with the most votes at that point is declared the winner.
If there is a tie, the person who got their last vote earliest wins.

Code Implementation

class TopVotedCandidate:

    def __init__(self, person_votes: list[int], times: list[int]):
        self.person_votes = person_votes
        self.times = times

    def q(self, time: int) -> int:
        # Find the relevant votes up to the query time.
        relevant_votes = []
        for i in range(len(self.times)):
            if self.times[i] <= time:
                relevant_votes.append((self.person_votes[i], self.times[i]))
            else:
                break

        vote_counts = {}
        leader = -1
        max_votes = -1

        # Tally the votes up to the given time.
        for person, _ in relevant_votes:
            vote_counts[person] = vote_counts.get(person, 0) + 1

        # Determine the leader based on vote counts and time.
        for person, _ in relevant_votes:
            if vote_counts[person] >= max_votes:
                # Update if new leader emerges or tie breaks
                if vote_counts[person] > max_votes:
                    leader = person
                    max_votes = vote_counts[person]
                
                #Tie-breaker: Candidate with latest vote wins.
                elif vote_counts[person] == max_votes and _ >= self.times.index(self.times[-1]):
                    leader = person

        return leader

Big(O) Analysis

Time Complexity

O(n*q) – For each query (q in total), we iterate through the entire votes array (of size n) from the beginning to the time specified in the query to count votes. This nested structure implies that, in the worst case, for each of the q queries, we might need to iterate through all n votes. Therefore, the total number of operations is proportional to n * q. This gives us a time complexity of O(n*q).

Space Complexity

O(1) – The brute force approach, as described, does not utilize any auxiliary data structures that scale with the input size. It iterates through the input arrays up to a specific time, but doesn't store intermediate counts or other information in a way that depends on the number of votes (N). Only a few counter variables are needed to track vote counts for each person, and these counters take up constant space regardless of the input size (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key idea is to keep track of who's winning the election as votes come in. We want to quickly find the leader at any given time without re-counting all the votes every time we're asked.

Here's how the algorithm would work step-by-step:

Process the votes one at a time and keep track of the current winner after each vote.
For each vote, check if it changes who's in the lead. If so, update our record of the leader at that time.
Store the leader and the time when they took or retained the lead.
When we need to find the leader at a specific time, search through our stored records to find the most recent leader at or before that time.
Since the times are in order, we can use a very efficient searching strategy that quickly narrows down the possibilities. This avoids checking every single record.

Code Implementation

class OnlineElection:

    def __init__(self, times, persons):
        self.leaders = []
        self.lead_times = []
        leader = -1
        leader_votes = {}

        for i in range(len(times)):
            time = times[i]
            person = persons[i]

            if person not in leader_votes:
                leader_votes[person] = 0

            leader_votes[person] += 1

            # Determine if current person is the new leader.
            if leader == -1 or leader_votes[person] >= leader_votes[leader]:
                if person != leader:

                    # Only update leader if it actually changes
                    leader = person
                    self.leaders.append(leader)
                    self.lead_times.append(time)

    def q(self, time):
        # Binary search for the latest time <= time
        left_index = 0
        right_index = len(self.lead_times) - 1
        ans = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2

            if self.lead_times[middle_index] <= time:
                ans = middle_index
                left_index = middle_index + 1
            else:
                right_index = middle_index - 1

        return self.leaders[ans]

Big(O) Analysis

Time Complexity

O(n + log n) – The constructor processes the votes array of size n once to determine the leader at each timestamp, taking O(n) time. The q method (finding the leader at a given time) uses binary search on the precomputed leaders and times, which takes O(log n) time. Thus the overall time complexity is O(n + log n), considering the constructor and a single query.

Space Complexity

O(N) – The algorithm stores the leader and the time when they took or retained the lead. This requires storing two lists of potentially N elements, where N is the number of votes. Thus, the auxiliary space used scales linearly with the number of votes. No other significant auxiliary data structures are used beyond these two lists, making the dominant space factor O(N).

Edge Cases

Case	How to Handle
Empty votes or times array	Return error or handle gracefully, as no leader can be determined.
Votes and times arrays have different lengths	Throw an exception or return an error code, indicating invalid input.
Times array is not strictly increasing	Handle this by either sorting times with corresponding votes, or by returning an error, depending on problem interpretation and requirements.
Query time is before the first election event.	Return -1 or a predefined value if there is no leader yet.
Query time is equal to one of the existing times.	Return the leader at that specific time index.
Many candidates with the same maximum vote count.	The implemented tie-breaking mechanism (favoring the candidate who achieved the vote count first) should correctly resolve this.
Large input arrays (votes and times) causing memory issues or slow performance.	Use binary search efficiently to locate the time and consider optimizing the storage of vote counts to minimize memory usage.
Integer overflow when counting votes for a candidate.	Use a larger data type (e.g., long) to store the vote counts if the number of votes can exceed the maximum value of an integer.

Empty votes or times array

How to Handle:

Return error or handle gracefully, as no leader can be determined.

Votes and times arrays have different lengths

How to Handle:

Throw an exception or return an error code, indicating invalid input.

Times array is not strictly increasing

How to Handle:

Handle this by either sorting times with corresponding votes, or by returning an error, depending on problem interpretation and requirements.

Query time is before the first election event.

How to Handle:

Return -1 or a predefined value if there is no leader yet.

Query time is equal to one of the existing times.

How to Handle:

Return the leader at that specific time index.

Many candidates with the same maximum vote count.

How to Handle:

The implemented tie-breaking mechanism (favoring the candidate who achieved the vote count first) should correctly resolve this.

Large input arrays (votes and times) causing memory issues or slow performance.

How to Handle:

Use binary search efficiently to locate the time and consider optimizing the storage of vote counts to minimize memory usage.

Integer overflow when counting votes for a candidate.

How to Handle:

Use a larger data type (e.g., long) to store the vote counts if the number of votes can exceed the maximum value of an integer.