911. Online Election

MediumDesignArrayHash TableBinary Search
Leetcode Link

Problem Description

The problem presents a scenario where we have a series of votes being cast at certain times for various candidates, represented by the persons array, where each vote is associated with a timestamp stored in the times array. We need to track who the leading candidate is at any given point in time, according to the timestamps of votes. When we're asked to find the leader at time t, we should include votes up to and including t.

Key points to note:

  • Each vote is for persons[i] at time times[i].
  • A query at time t should return the person leading the election at that time.
  • If there's a tie, the person who received the latest vote (of the tied candidates) is considered the leader.

There are two parts to solving this problem:

  1. We need a system to track the leading candidate at any time.
  2. We need an efficient way to answer the query for the leader at a specific time t.

We must construct a class TopVotedCandidate with two methods: a constructor to prepare our data structures for tracking the votes, and a method q(t) to find the leading candidate at time t.

Intuition

For the solution, we use two main approaches:

  1. Preprocessing the votes in the constructor to know the current leader after each vote is cast.

    The intuition here is to iterate through all votes in chronological order and maintain a running count of the votes each person received. A hash map or counter is used to keep track of the votes. We'll keep track of the maximum votes received so far, and whenever a candidate's vote count ties with or exceeds the current max, we update who the current leader is. By doing this, we automatically handle the tiebreaker rule where the most recent vote wins in case of a tie.

    To efficiently answer the query later, we create an array (self.wins) that holds the leader at the time of each vote cast, and an array (self.times) which is the same as times provided in the input. At the end of the constructor, we have a complete mapping of times to the leader at that point.

  2. Implementing the query method q(t) with a binary search.

    The reason behind using binary search is that we have a sorted list of times and want to quickly find the last time at or before t (as votes are counted up to and including time t). Binary search allows us to efficiently find this point with O(log n) complexity, where n is the number of votes.

    Once we perform the binary search in the self.times array, we find the index where the time is just equal to or less than t. We return the corresponding leader from self.wins.

Combining these two methods, we can quickly and accurately determine the leading candidate for each query.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The solution approach utilizes several concepts from computer science, specifically data structures such as hash maps (also referred to as dictionaries or counters in some languages) and algorithms such as binary search.

Here is the breakdown of the implementation:

Constructor: __init__(self, persons: List[int], times: List[int])

  1. Initialize Variables:

    • mx: A variable to keep track of the maximum number of votes any person has at any point.
    • cur: A variable to store the person who is currently leading the election.
    • counter: It's a Counter object from the collections module which acts as a hash map to count votes for each person.
    • self.times: Stores the times when votes were cast, directly taken from the input.
    • self.wins: An empty list that we will populate with the person leading after each vote.

  2. Count Votes and Record Leaders:

    • We loop through persons array with indices to access both the person and the corresponding time of the vote.
    • Each time a person receives a vote, we increment their count in counter.
    • If the person's updated vote count is at least as much as mx, we update mx to this new count and cur to the current person.
    • Then, we append cur to self.wins, which ensures that self.wins holds the leader after each vote is cast.

Method: q(self, t: int) -> int

  1. Binary Search:

    • We need to find the latest time that does not exceed t in self.times and get the leading person at that time from self.wins.
    • Initialize left to index 0 and right to the last index of self.wins.
    • We execute a loop while left is less than right to narrow down the search space.
    • In each iteration, we calculate the middle index, mid, using the formula (left + right + 1) >> 1. The +1 ensures that we favor the right part in the search to find the last occurrence, and >> 1 is a bitwise operation for integer division by 2.
    • If the time at mid is less than or equal to t, we move left up to mid since we want to include votes cast at time t.
    • If the time at mid is greater than t, we move right down to mid - 1.
    • The loop continues until left and right converge to a single element which is the largest time less than or equal to t.

  2. Return the Leader:

    • After the loop ends, left will point to the required index in self.wins.
    • We return self.wins[left] as the answer, which gives us the leader at time t.

This approach ensures that the initialization of the TopVotedCandidate class preprocesses the votes for quick retrieval, and q method uses binary search to efficiently answer queries about the leader at any given time t.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Assume we have the following input:

  • persons array: [1, 2, 1, 3, 3]
  • times array: [0, 10, 20, 30, 40]

When we construct a new TopVotedCandidate object with the above input, it processes the input arrays as follows:

  1. Initialize Variables:
  • mx is set to 0. It will keep track of the maximum votes received by any candidate.
  • cur is None since initially, no votes have been cast.
  • counter is an empty Counter object.
  • self.times is set to the times array: [0, 10, 20, 30, 40].
  • self.wins is initialized as an empty list.
  1. Count Votes and Record Leaders:
  • Votes are counted one by one:
    • First vote is for person 1 at time 0. We update the counter {1: 1}. Since 1 > mx (0), mx becomes 1 and cur becomes 1. self.wins is now [1].
    • Second vote is for person 2 at time 10. The counter becomes {1: 1, 2: 1}. Since 1 (votes for person 2) ≥ mx (1), mx remains 1 and cur becomes 2 due to the most recent vote tiebreaker rule. self.wins becomes [1, 2].
    • The third vote is for person 1 at time 20. Counter gets updated to {1: 2, 2: 1}. Person 1 now has more votes than person 2, so mx is now 2 and cur is 1. self.wins is now [1, 2, 1].
    • The fourth vote is for person 3 at time 30. The counter is {1: 2, 2: 1, 3: 1}. Since person 3's votes 1 is not ≥ mx 2, cur remains 1. self.wins remains [1, 2, 1].
    • The fifth vote is for person 3 at time 40. The counter updates to {1: 2, 2: 1, 3: 2}. Now person 3's votes match the current maximum, but since the vote is the latest, person 3 becomes the leader. self.wins is now [1, 2, 1, 1, 3].

After construction, if we query at time t = 25, we must find the leader up to that time.

  1. Binary Search:
  • We will run a binary search on self.times to find the largest time not exceeding t.
  • Initialize left to 0 and right to 4 (the last index of self.times).
  • The binary search converges, and we find that index 2 (time 20) is the correct index for time t = 25.
  1. Return the Leader:
  • We observed self.wins[2] is 1, so person 1 is returned as the leader at time t = 25.

Constructing the TopVotedCandidate allowed us to tabulate the leaders efficiently, and querying with a binary search provided us the desired information quickly.

Solution Implementation

1from collections import Counter
2
3class TopVotedCandidate:
4  
5    def __init__(self, persons: List[int], times: List[int]):
6        """
7        Initializes the TopVotedCandidate object, preprocesses the leading candidates, and stores for querying later.
8        Args:
9        persons (List[int]): List of people who are voting.
10        times (List[int]): The time at which the persons' votes are cast.
11        """
12        max_votes = current_leader = 0  # Initialize the variables to store maximum votes and current leading candidate.
13        vote_counts = Counter()  # A counter to keep track of votes for each candidate.
14        self.times = times  # Store the times list for binary search during querying.
15        self.leaders = []  # List to store the leader at each time.
16      
17        for index, person in enumerate(persons):
18            vote_counts[person] += 1
19            # Update the current leader if the person has equal or more votes than max_votes.
20            if vote_counts[person] >= max_votes:
21                max_votes, current_leader = vote_counts[person], person
22            # Append the current leader to the leaders list.
23            self.leaders.append(current_leader)
24
25    def q(self, time: int) -> int:
26        """
27        Answer a query to find the top voted candidate at time 't'.
28        Args:
29        time (int): The time at which we want to find the top voted candidate.
30        Returns:
31        int: The candidate who was leading at time 't'.
32        """
33        # Conduct a binary search to find the right-most time that is less than or equal to 'time'.
34        left, right = 0, len(self.leaders) - 1
35        while left < right:
36            mid = (left + right + 1) // 2  # Take the upper middle to prevent infinite loop with two elements.
37            if self.times[mid] <= time:
38                left = mid
39            else:
40                right = mid - 1
41        # Return the leader at the found time.    
42        return self.leaders[left]
43
1class TopVotedCandidate {
2    private int[] votingTimes;
3    private int[] leadingCandidates;
4
5    // Constructor to initialize the TopVotedCandidate with persons array and times array.
6    // It calculates the current leading candidate at each voting time.
7    public TopVotedCandidate(int[] persons, int[] times) {
8        int length = persons.length;
9        int maxVotes = 0;
10        int currentLeader = 0;
11        this.votingTimes = times;
12        leadingCandidates = new int[length];
13        int[] voteCounter = new int[length]; // Array to keep track of votes for each person.
14      
15        for (int i = 0; i < length; ++i) {
16            int person = persons[i];
17            // Increment vote count for the current person and check if they are the new leader.
18            if (++voteCounter[person] >= maxVotes) {
19                maxVotes = voteCounter[person];
20                currentLeader = person;
21            }
22            leadingCandidates[i] = currentLeader; // Update current leader.
23        }
24    }
25
26    // This method returns the top-voted candidate at a given time `t`.
27    // If `t` is between two times in the votingTimes array, return the top-voted candidate at the latest recorded time before `t`.
28    public int q(int t) {
29        int left = 0;
30        int right = leadingCandidates.length - 1;
31        // Binary search to find the closest time without going over.
32        while (left < right) {
33            int mid = (left + right + 1) >>> 1;
34            if (votingTimes[mid] <= t) {
35                left = mid;
36            } else {
37                right = mid - 1;
38            }
39        }
40        return leadingCandidates[left]; // Return the leader at the found time.
41    }
42}
43
44/**
45 * Your TopVotedCandidate object will be instantiated and called as such:
46 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
47 * int param_1 = obj.q(t);
48 */
49
1#include <vector>
2
3using std::vector;
4
5class TopVotedCandidate {
6public:
7    // Stores the specific times when votes are cast
8    vector<int> voteTimes;
9    // Stores the candidate id with the most votes up to the corresponding time
10    vector<int> leadingCandidates;
11
12    // Constructor
13    TopVotedCandidate(vector<int>& persons, vector<int>& times) : voteTimes(times) {
14        int numberOfVotes = persons.size();
15        leadingCandidates.resize(numberOfVotes);
16        int maxVotes = 0; // Tracks the most votes any candidate has at a certain point
17        int currentWinner = -1; // Tracks the current winning candidate
18        vector<int> votesCount(numberOfVotes, 0); // Counter for the votes each candidate receives
19
20        // Iterate through all the votes
21        for (int i = 0; i < numberOfVotes; ++i) {
22            int personId = persons[i];
23          
24            // Increment the corresponding candidate's vote count
25            votesCount[personId]++;
26
27            // Check if the current candidate has equal to or more votes than the max
28            if (votesCount[personId] >= maxVotes) {
29                maxVotes = votesCount[personId]; // Update the max votes
30                currentWinner = personId; // Update the current winner
31            }
32
33            // Record the leading candidate at the ith time
34            leadingCandidates[i] = currentWinner;
35        }
36    }
37
38    // Returns the candidate id that was leading at time t.
39    int q(int t) {
40        // Binary search for the right index because the votes are recorded in time order
41        int left = 0;
42        int right = leadingCandidates.size() - 1;
43        while (left < right) {
44            int mid = (left + right + 1) / 2;
45            if (voteTimes[mid] <= t) {
46                left = mid; // Mid is a valid position, move left up to mid
47            } else {
48                right = mid - 1; // Mid is not valid, search in the left section
49            }
50        }
51        // Once the binary search finishes, 'left' will point at the largest time <= t
52        return leadingCandidates[left];
53    }
54};
55
56/**
57 * Your TopVotedCandidate object will be instantiated and called as such:
58 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
59 * int result = obj->q(t);
60 */
61
1// Requires TypeScript's support for tuples, features introduced in ES6, and ES6 map objects
2
3// Declare global variables to maintain the state
4let voteTimes: number[] = [];
5let leadingCandidates: number[] = [];
6let votesCount: Map<number, number> = new Map(); // Using a Map to count votes for scalability
7let maxVotes: number = 0;
8let currentWinner: number = -1;
9
10// Initialize the state with the persons and times array
11function initialize(persons: number[], times: number[]): void {
12    voteTimes = times;
13    for (let i = 0; i < persons.length; ++i) {
14        votesCount.set(persons[i], 0);
15    }
16    leadingCandidates = new Array(times.length).fill(-1);
17}
18
19// Processes the votes and updates the state
20function processVotes(persons: number[]): void {
21    persons.forEach((personId, i) => {
22        let count = votesCount.get(personId) || 0;
23        votesCount.set(personId, count + 1);
24
25        if (count + 1 >= maxVotes) {
26            maxVotes = count + 1;
27            currentWinner = personId;
28        }
29
30        leadingCandidates[i] = currentWinner;
31    });
32}
33
34// Function to initialize, it emulates the constructor logic
35function topVotedCandidate(persons: number[], times: number[]): void {
36    initialize(persons, times);
37    processVotes(persons);
38}
39
40// Function that emulates the q method in the original class
41function q(t: number): number {
42    let left = 0;
43    let right = leadingCandidates.length - 1;
44
45    while (left < right) {
46        let mid = Math.floor((left + right + 1) / 2);
47        if (voteTimes[mid] <= t) {
48            left = mid;
49        } else {
50            right = mid - 1;
51        }
52    }
53
54    return leadingCandidates[left];
55}
56
57// Example of usage
58let persons = [0, 1, 1, 0, 0, 1, 0];
59let times = [0, 5, 10, 15, 20, 25, 30];
60topVotedCandidate(persons, times); // Initialize state
61console.log(q(3));  // Should return the candidate id that was leading at time 3
62console.log(q(12)); // Should return the candidate id that was leading at time 12
63
Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity:

  • The __init__ method has a time complexity of O(N) where N is the number of votes (the length of the persons and times lists). This accounts for iterating over all the votes once and updating the counter each time.

  • The q method performs a binary search which has a time complexity of O(log N), where N is the number of elements in self.times or self.wins since both lists are of the same length.

Space Complexity:

  • The space complexity of the __init__ method is O(N) where N is the number of votes. This is because we store two lists, self.times and self.wins, both of which contain N elements. Additionally, there is a counter that in the worst-case scenario could have as many keys as there are votes, therefore its size is also O(N).

  • The q method does not use any additional space other than a few variables for the binary search, which means its space complexity is O(1) as it does not depend on the size of the input.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫