Skip to main content

Binary Search

Online Election Solution In C++/Java/Python/JS

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.

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.
Illustration of Online Election Problem Description

Examples:

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] <= 109
  • times is sorted in a strictly increasing order.
  • times[0] <= t <= 109
  • At most 104 calls will be made to q.

Online Selection Description

In this problem, you are given two integer arrays, persons and times, representing an election process. The persons[i] array stores the candidate who received a vote at the corresponding time times[i].
The goal is to determine which candidate was leading the election at any given query time t. If two or more candidates have the same highest number of votes, the most recent vote determines the leader.
To solve this, you need to implement a TopVotedCandidate class. The constructor will initialize the persons and times arrays.
The q(int t) function will return the candidate with the most votes at time t by checking the voting history up to that time. If there is a tie, the candidate who received the most recent vote will be declared the leader.

Brute Force Approach

Intuition:

We are given two arrays — persons and times — and some queries. The persons[i] array represents the person who received a vote at time times[i]. For each query, we are tasked with finding which person had the most votes at a given time t.

If there’s a tie (two or more people have the same number of votes), the person who received the most recent vote should be considered the leader.

Initial Thought Process:

The first approach that comes to mind is to simulate the process directly.

For each query, we can go through the persons array and check which votes were cast at or before time t. This way, we can keep track of two variables.

  • The number of votes each person has received is determined using a frequency counter.
  • The current leader (the person with the most votes) and the maximum vote count.

How to Track the Leader?

To track the leader, we can maintain two variables. One variable will store the maximum vote count at any given time, and the other will store the person with the maximum votes.

As we process each vote, we increase the vote count for the corresponding person. If the new vote count exceeds the current maximum, we update both the maximum count and the person holding that count. If the vote count equals the current maximum, we give preference to the person who received the most recent vote, as the problem states that ties should be broken this way.

Why This Works...

This approach works because we are processing the votes in the order they were cast, which naturally allows us to handle tie-breaking correctly. The most recent vote will always override a previous tie, ensuring that the latest leading candidate is accurately recorded.

Example

persons = [1, 2, 1, 3, 3], times = [5, 10, 15, 20, 25].

If we query q(15), Person 1 will be leading with 2 votes.

If we query q(22), Person 3 will be leading with 2 votes because they received the most recent vote at time 20.

The direct simulation makes it easy to understand and implement, while the tie-breaking rule is automatically handled by the order of processing.

Illustration of Online Election Brute Force Approach 1
Illustration of Online Election Brute Force Approach 2

Online Election Example

Input: persons = [2, 3, 1, 3, 2], times = [2, 5, 8, 12, 15] , q(4), q(10), q(15)
Output: [null, 2, 1, 2]

Step 1: Initialization

In the TopVotedCandidate object, we initialized the input arrays:

  • persons = [2, 3, 1, 3, 2]
  • times = [2, 5, 8, 12, 15]

The constructor assigns these arrays to the class members.

Step 2: Query Execution

Let's test a few q(t) queries:

q(4):

  • Reset freq[] → `[0, 0, 0, 0, 0]
  • maxCount = 0, maxCountPerson = 0

Iteration through the loop:

  1. i = 0:
    • times[0] = 2 ≤ 4
    • freq[2]++ → [0, 0, 1, 0, 0]
    • maxCount = 1, maxCountPerson = 2
  2. i = 1:
    • times[1] = 5 > 4 → Stop loop
  • Output: 2

q(10):

  • Reset freq[] → [0, 0, 0, 0, 0]
  • maxCount = 0, maxCountPerson = 0

Iteration through the loop:

  1. i = 0:
    • times[0] = 2 ≤ 10
    • freq[2]++ → [0, 0, 1, 0, 0]
    • maxCount = 1, maxCountPerson = 2
  2. i = 1:
    • times[1] = 5 ≤ 10
    • freq[3]++ → [0, 0, 1, 1, 0]
    • Since freq[3] = freq[2], last vote was for 3, maxCountPerson = 3
  3. i = 2:
    • times[2] = 8 ≤ 10
    • freq[1]++ → [0, 1, 1, 1, 0]
    • Since freq[1] = freq[3], last vote was for 1, maxCountPerson = 1
  4. i = 3:
    • times[3] = 12 > 10 → Stop loop
  • Output: 1

q(15):

  • Reset freq[] → [0, 0, 0, 0, 0]
  • maxCount = 0, maxCountPerson = 0

Iteration through the loop:

  1. i = 0:
    • times[0] = 2 ≤ 15
    • freq[2]++ → [0, 0, 1, 0, 0]
    • maxCount = 1, maxCountPerson = 2
  2. i = 1:
    • times[1] = 5 ≤ 15
    • freq[3]++ → `[0, 0, 1, 1, 0]
    • Since freq[3] = freq[2], last vote was for 3 → maxCountPerson = 3
  3. i = 2:
    • times[2] = 8 ≤ 15
    • freq[1]++ → [0, 1, 1, 1, 0]
    • maxCountPerson = 3
  4. i = 3:
    • times[3] = 12 ≤ 15
    • freq[3]++ → [0, 1, 1, 2, 0]
    • maxCount = 2, maxCountPerson = 3
  5. i = 4:
    • times[4] = 15 ≤ 15
    • freq[2]++ → [0, 1, 2, 2, 0]
    • Since freq[2] = freq[3] = 2, but last vote was for 2 →maxCountPerson = 2
  • Output: 2

Final Outputs:

q(4) → 2
q(10) → 1
q(15) → 2

Online Election Algorithm

1. Constructor (TopVotedCandidate)

Step 1: Write the Constructor

  • Assign the input vectors to the class variables using the this-> keyword.
  • This ensures that the persons and times arrays are available for use in the q(int t) function.


2. q(int t) Function

Step 1: Create Necessary Variables

  • Create an integer n to store the size of the persons array.
  • Create a freq[] array to store the count of votes for each person.
  • Create two variables:
    • maxCount → To track the highest number of votes.
    • maxCountPerson → To store the person with the highest votes.


Step 2: Loop Through Votes Until Time t

  • Iterate through the persons array:
    • If times[i] > t, stop the loop since we only care about votes up to or before time t.
    • Increment the vote count for persons[i].
    • If the updated vote count is greater than or equal to maxCount, update maxCount and maxCountPerson.


Step 4: Return the Person with the Maximum Votes

  • After the loop ends, return maxCountPerson since it holds the leading candidate.

Online Election Solution
Online Election solution in C++
class TopVotedCandidate {
public:
    vector<int> persons;
    vector<int> times;

    // Constructor to initialize persons and times
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        this->persons = persons;
        this->times = times;
    }
    
    // Function to return the top-voted candidate at time t
    int q(int t) {
        int n = persons.size();
        vector<int> freq(n, 0);
        int maxCount = 0;
        int maxCountPerson = 0;

        // Iterating through votes
        for (int i = 0; i < n; ++i) {
            if (times[i] > t) break;
            freq[persons[i]]++;

            // Updating the max voted candidate
            if (freq[persons[i]] >= maxCount) {
                maxCount = freq[persons[i]];
                maxCountPerson = persons[i];
            }
        }
        return maxCountPerson;
    }
};

Online Election solution in Java
class TopVotedCandidate {
    private int[] persons;
    private int[] times;

    // Constructor to initialize persons and times arrays
    public TopVotedCandidate(int[] persons, int[] times) {
        this.persons = persons;
        this.times = times;
    }

    // Function to return the top-voted candidate at time t
    public int q(int t) {
        int n = persons.length;
        int[] freq = new int[n];
        int maxCount = 0;
        int maxCountPerson = 0;

        // Iterating through votes
        for (int i = 0; i < n; i++) {
            if (times[i] > t) break;
            freq[persons[i]]++;

            // Updating the max voted candidate
            if (freq[persons[i]] >= maxCount) {
                maxCount = freq[persons[i]];
                maxCountPerson = persons[i];
            }
        }
        return maxCountPerson;
    }
}

Online Election solution in Python
class TopVotedCandidate:
    # Constructor to initialize persons and times lists
    def __init__(self, persons: List[int], times: List[int]):
        

        self.persons = persons
        self.times = times

    # Function to return the top-voted candidate at time t
    def q(self, t: int) -> int:
        n = len(self.persons)
        freq = [0] * n
        max_count = 0
        max_count_person = 0

        # Iterating through votes
        for i in range(n):
            if self.times[i] > t:
                break
            freq[self.persons[i]] += 1

            # Updating the max voted candidate
            if freq[self.persons[i]] >= max_count:
                max_count = freq[self.persons[i]]
                max_count_person = self.persons[i]

        return max_count_person

Online Election solution in Javascript
/**
 * Constructor function to initialize the class
 * @param {number[]} persons - List of persons receiving votes
 * @param {number[]} times - List of timestamps when votes were cast
 */
var TopVotedCandidate = function(persons, times) {
    // Store the input persons and times as class properties
    this.persons = persons;
    this.times = times;
};

/** 
 * Function to find the person with the most votes at time t
 * @param {number} t - The given time query
 * @return {number} - The person with the maximum votes at time t
 */
TopVotedCandidate.prototype.q = function(t) {
    // Get the number of persons
    let n = this.persons.length;

    // Frequency array to store the vote count of each person
    let freq = new Array(n).fill(0);

    // Variables to track the person with the highest votes
    let maxCount = 0;
    let maxCountPerson = 0;

    // Iterate through all votes
    for (let i = 0; i < n; i++) {
        // Stop searching if we exceed the given time
        if (this.times[i] > t) break;

        // Increment the vote count for the current person
        freq[this.persons[i]]++;

        // Update the maxCountPerson if the current person has more or equal votes
        if (freq[this.persons[i]] >= maxCount) {
            maxCount = freq[this.persons[i]];
            maxCountPerson = this.persons[i];
        }
    }

    // Return the person who had the highest votes at time t
    return maxCountPerson;
};

Online Election Complexity Analysis

Time Complexity: O(q×n)

Let's analyze the time complexity of both the constructor and the q(int t) function separately.

1. Constructor

Copying the persons and times vectors to the class variables takes O(n) time, where n is the size of the input vectors.

  • Therefore, the time complexity of the constructor is O(n)

2. q(int t) Function

  1. Initializing the freq[] array takes O(n) time.
  2. The loop runs until the first times[i] > t is encountered.
    • In the worst case, if t is greater than the last value of times[], the loop will run n times.
    • Counting the votes and updating maxCount and maxCountPerson inside the loop takes O(1) time.

Therefore, the worst-case time complexity of q(int t) is O(n).

If we assume the total number of queries q, then the time taken is O(q×n).

Space Complexity: O(n)

1. Auxiliary Space Complexity

Auxiliary space refers to the extra space used during the execution of the program (excluding the input size).

Constructor:

  • No additional space is used in the constructor apart from storing input values.
  • Auxiliary space in the constructor → O(1)

q(int t) Function:

  • freq[] is a vector of size n → O(n)
  • maxCount and maxCountPerson are integer variables → O(1)

Total auxiliary space for q(int t) = O(n) + O(1) = O(n)

2. Total Space Complexity

Total space includes both the input size and any extra space used.

Constructor:

  • Storing persons and times vectors → O(n) + O(n) = O(n)

During q(int t):

  • Additional space for freq[] and other variables → O(n)

Total space complexity = O(n) + O(n) = O(n)


Is the brute force solution efficient?

If we look at the complexity of the brute force solution, it is O(q × n), where q is the number of queries and n is the length of the persons array. This means that for each query, we are performing an O(n) computation to find the leading candidate at time t.

The problem allows up to 10⁴ (10,000) queries, and the size of the persons array can go up to 5000. So, in the worst case, the total number of operations would be around 5 × 10⁷ (50 million). While this might seem large, modern systems can handle this level of computation within a reasonable time. However, it is still not very efficient, especially if the input size increases further or if the queries are frequent.

Since the brute force approach recalculates the leader from scratch for every query, it leads to unnecessary repeated work. This makes it slower compared to more optimized approaches that could use precomputation or binary search to speed things up. Therefore, while the brute force solution works, it is not the most efficient way to solve the problem for large inputs.


Optimal Approach

Intuition:

It's clear that an O(q × n) solution will be too slow for large inputs, so we need to find a way to reduce the complexity.

Since the number of queries q is controlled by the driver code, we can't change that part, but we can focus on improving the n part.

Right now, the problem is that for every query, we are looping through all the votes to find the leading candidate, which is inefficient.

So, we need to think about how we can avoid this repeated work. Instead of recalculating the leader from scratch each time, maybe we can precompute or store the results in a way that allows us to quickly determine the leader at any given time.

Can we use some kind of search or lookup to make this faster?

We know that the times array is sorted in non-decreasing order, which means the votes are recorded in the order they were cast. The value times[i] represents the time when persons[i] received a vote.

Now, imagine creating an array where each index i stores the person who had the most votes at time times[i]. This means that at any time t, if we can quickly find the largest times[i] that is less than or equal to t, we can directly look up the person with the most votes at that time and return it.

This would save us from counting votes repeatedly for each query, since the information about the leading candidate at each time is already stored.

Our first goal is to create an array maxVotedPersons that will store the person with the highest number of votes at each index i. This will help us quickly find the leading person at any given time.

How to compute maxVotedPersons array?

We can handle this directly in the constructor, TopVotedCandidate. To achieve this, we can maintain a helper array, freq where freq[i] will store the number of votes received by person i. Along with this, we’ll keep two variables:

  • maxCount → to track the highest number of votes any person has received so far.
  • maxCountPerson → to store the person with the highest votes so far.

We’ll then iterate through all values of i from 0 to n-1. At every iteration, we will update freq[persons[i]], and based on it, we will update maxCount and maxCountPerson. Finally, we store maxCountPerson in the maxVotedPersons array.

Illustration of How to compute maxVotedPersons array.

Example:

persons = [1, 2, 1, 3, 2]
times = [5, 10, 15, 20, 25]

maxVotedPersons = [1, 2, 1, 1, 2]

You can see that at times[3], which is 20, the maxVotedPersons[3] is 1, which means 1 is the person with the maximum votes at time 20.

Now that we've computed maxVotedPersons, the next step is to efficiently find the largest times[i] that is less than or equal to t in q(int t). Since the times array is sorted, we can search for the right index quickly. Once we find the index, we can directly return maxVotedPersons[index] as the person with the highest votes at that time.

How to find the largest times[i] which is less than or equal to t?

To find the largest times[i] that is less than or equal to t, we can take advantage of the fact that the times array is sorted. This means that at any point, we can narrow down the search to either the left or right side of the current position based on the value at that point.

Let's say we pick the middle index (mid) of the times array. The value at times[mid] will either be greater than t or less than or equal to t.

Case 1: If times[mid] is less than or equal to t:

It means that times[mid] is a possible candidate for the largest value less than or equal to t. But we’re not certain it's the largest, so we need to keep searching on the right side to see if there’s a larger valid value.

Example:
times = [1, 3, 5, 6, 9], t = 6

  • mid = 2, times[mid] = 5
  • Since 5 ≤ 6, it’s a possible answer, but we check the right side to see if there's a larger value ≤ 6.
Illustration of Online Election Optimal Approach Case 1.

Case 2: If times[mid] is greater than t

It means that times[mid] and everything to its right is too large to be a valid answer. Therefore, we should search on the left side.

Example:
times = [1, 3, 5, 7, 9], t = 4

  • mid = 2, times[mid] = 5
  • Since 5 > 4, we know that any value to the right will also be greater than 4, so we focus on the left side.

By adjusting our search range based on these cases, we can quickly find the largest times[i] that is less than or equal to t.

Illustration of Online Election Optimal Approach Case 2.

Online Election Algorithm

To write the same in code, we start by initializing two variables, low and high, set to 0 and n - 1, respectively. Here, low represents the starting index of the search space, and high represents the ending index.

We also create a variable idx, initially set to -1. After the search process, idx will store the largest index where times[idx]t.

We calculate mid as the average of low and high. Then we compare times[mid] with t and handle the cases:

  • If times[mid]t, we update idx = mid as a possible answer and shift low to mid + 1 to search for a larger valid index.
  • If `times[mid] > t, we know that the value is too large, so we shift high to mid - 1 to search on the left side.

This process continues until low and high surpass each other. The algorithm will end with idx storing the required value. Finally, we return the value of maxVotedPerson at that idx.

This method of narrowing down the search space by computing on the basis of the middle index is called binary search. It is much faster than linear search.

Here you can read about binary search in more detail.

0:00
/1:55

Animation of Online Election Optimal Approach.

Online Election Example

Input: persons = [2, 3, 1, 3, 2], times = [2, 5, 8, 12, 15] , q(4), q(10), q(15)
Output: [null, 2, 1, 2]

Step 1: Constructing TopVotedCandidate object

Initialization:

  • n = persons.size() = 5
  • times = [2, 5, 8, 12, 15]
  • freq array initialized: [0, 0, 0, 0, 0] (since n=5)
  • Variables:
    • maxCount = 0
    • maxCountPerson = 0
    • maxFreqPersons = []

Building maxFreqPersons

We iterate over each i from 0 to 4 and update freq, maxCount, and maxCountPerson.

Iteration 1 (i = 0)

  • Vote for persons[0] = 2
  • freq[2]++ → freq = [0, 0, 1, 0, 0]
  • maxCount = 1, maxCountPerson = 2
  • maxFreqPersons = [2]

Iteration 2 (i = 1)

  • Vote for persons[1] = 3
  • freq[3]++ → freq = [0, 0, 1, 1, 0]
  • Since freq[3] = maxCount, we update maxCountPerson = 3
  • maxFreqPersons = [2, 3]

Iteration 3 (i = 2)

  • Vote for persons[2] = 1
  • freq[1]++ → freq = [0, 1, 1, 1, 0]
  • Since freq[1] = maxCount, we update maxCountPerson = 1
  • maxFreqPersons = [2, 3, 1]

Iteration 4 (i = 3)

  • Vote for persons[3] = 3
  • freq[3]++ → freq = [0, 1, 1, 2, 0]
  • Since freq[3] > maxCount, update maxCount = 2, maxCountPerson = 3
  • maxFreqPersons = [2, 3, 1, 3]

Iteration 5 (i = 4)

  • Vote for persons[4] = 2
  • freq[2]++ → freq = [0, 1, 2, 2, 0]
  • Since freq[2] = maxCount, update maxCountPerson = 2
  • maxFreqPersons = [2, 3, 1, 3, 2]

Step 2: Processing Queries

Now, we answer queries using the q(int t) function.

Query: q(4)

Find the largest times[i] ≤ 4.

Binary Search for t = 4

  • low = 0, high = 4, idx = -1
  • mid = (0 + 4) / 2 = 2, times[2] = 8 (greater than 4), move high = 1
  • mid = (0 + 1) / 2 = 0, times[0] = 2 (≤ 4), update idx = 0, move low = 1
  • mid = (1 + 1) / 2 = 1, times[1] = 5 (greater than 4), move high = 0
  • Final idx = 0, return maxFreqPersons[0] = 2

Output: 2

Query: q(10)

Find the largest times[i] ≤ 10.

Binary Search for t = 10

  • low = 0, high = 4, idx = -1
  • mid = (0 + 4) / 2 = 2, times[2] = 8 (≤ 10), update idx = 2, move low = 3
  • mid = (3 + 4) / 2 = 3, times[3] = 12 (greater than 10), move high = 2
  • Final idx = 2, return maxFreqPersons[2] = 1

Output: 1

Query: q(15)

Find the largest times[i] ≤ 15.

Binary Search for t = 15

  • low = 0, high = 4, idx = -1
  • mid = (0 + 4) / 2 = 2, times[2] = 8 (≤ 15), update idx = 2, move low = 3
  • mid = (3 + 4) / 2 = 3, times[3] = 12 (≤ 15), update idx = 3, move low = 4
  • mid = (4 + 4) / 2 = 4, times[4] = 15 (≤ 15), update idx = 4, move `low = 5
  • Final idx = 4, return maxFreqPersons[4] = 2

Output: 2

Final Output: [null, 2, 1, 2]

  • null for the constructor.
  • 2 for q(4).
  • 1 for q(10).
  • 2 for q(15).

Online Election Algorithm

Step 1: Define the Member Variables

  • maxFreqPersons to store the leader at each timestamp.
  • times to store the timestamps.

Step 2: Implement the Constructor

  • Initialize maxFreqPersons and times.
    Create a frequency map to count votes for each person.
  • Track the person with the highest votes using maxCount and maxCountPerson.

Step 3: Process Each Vote

  • Iterate through persons and update their vote count in the frequency map.
  • Check if the current person’s count is the highest.
    If yes, update maxCountPerson
  • Store the leader at each step in maxFreqPersons.

Step 4: Implement the Query Function q(t)

  • Initialize low, high, and idx to perform a search.
  • Use an efficient search to find the largest times[i] that is ≤ t.

Step 5: Compare times[mid] with t

  • If times[mid] ≤ t, store mid as a potential answer and move right.
    If times[mid] > t, move left.

Step 6: Return the Result

  • Return the leader at maxFreqPersons[idx].
    If no valid index is found, return -1.

This structure ensures efficient precomputation and fast query processing.

Online Election Leetcode Solution
Online Election solution in C++
class TopVotedCandidate {
public:
    vector<int> maxFreqPersons;
    vector<int> times;

    // Constructor to process votes and store the leading candidates at each timestamp
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int n = persons.size();
        this->times = times;
        vector<int> freq(n, 0);
        int maxCount = 0;
        int maxCountPerson = 0;

        for (int i = 0; i < n; ++i) {
            // Increment the vote count for the current person
            freq[persons[i]]++;

            // Update the most voted person
            if (freq[persons[i]] >= maxCount) {
                maxCount = freq[persons[i]];
                maxCountPerson = persons[i];
            }

            // Store the leader at this timestamp
            maxFreqPersons.push_back(maxCountPerson);
        }
    }
    
    // Query function to find the top-voted person at a given time t
    int q(int t) {
        int n = times.size();
        int low = 0, high = n - 1, idx = -1;

        // Binary search to find the largest time <= t
        while (low <= high) {
            int mid = (low + high) / 2;
            if (times[mid] <= t) {
                idx = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // Return the leading candidate at the found index
        return (idx == -1) ? 0 : maxFreqPersons[idx];
    }
};

Online Election solution in Java
class TopVotedCandidate {
    private List<Integer> maxFreqPersons;
    private List<Integer> times;

    // Constructor to process votes and store the leading candidates at each timestamp
    public TopVotedCandidate(int[] persons, int[] times) {
        int n = persons.length;
        this.times = new ArrayList<>();
        this.maxFreqPersons = new ArrayList<>();
        int[] freq = new int[n];
        int maxCount = 0;
        int maxCountPerson = 0;

        for (int i = 0; i < n; i++) {
            this.times.add(times[i]);
            freq[persons[i]]++;

            if (freq[persons[i]] >= maxCount) {
                maxCount = freq[persons[i]];
                maxCountPerson = persons[i];
            }

            this.maxFreqPersons.add(maxCountPerson);
        }
    }

    // Query function to find the top-voted person at a given time t
    public int q(int t) {
        int low = 0, high = times.size() - 1, idx = -1;

        // Binary search to find the largest time <= t
        while (low <= high) {
            int mid = (low + high) / 2;
            if (times.get(mid) <= t) {
                idx = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // Return the leading candidate at the found index
        return (idx == -1) ? 0 : maxFreqPersons.get(idx);
    }
}

Online Election solution in Python
class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        # Store the times array
        self.times = times
        self.maxFreqPersons = []
        freq = [0] * len(persons)
        max_count = 0
        max_count_person = 0

        # Process votes and store the leading candidate at each timestamp
        for i in range(len(persons)):
            freq[persons[i]] += 1
            
            if freq[persons[i]] >= max_count:
                max_count = freq[persons[i]]
                max_count_person = persons[i]

            self.maxFreqPersons.append(max_count_person)

    def q(self, t: int) -> int:
        low, high, idx = 0, len(self.times) - 1, -1

        # Binary search to find the largest time <= t
        while low <= high:
            mid = (low + high) // 2
            if self.times[mid] <= t:
                idx = mid
                low = mid + 1
            else:
                high = mid - 1

        # Return the leading candidate at the found index
        return 0 if idx == -1 else self.maxFreqPersons[idx]

Online Election solution in Javascript
/**
 * @param {number[]} persons - Array representing votes at different timestamps
 * @param {number[]} times - Array representing timestamps at which votes were cast
 */
var TopVotedCandidate = function(persons, times) {
    // Store the times array for future queries
    this.times = times;

    // Array to store the most voted person at each timestamp
    this.maxFreqPersons = [];

    // Frequency map to keep track of votes for each candidate
    let freq = new Array(persons.length).fill(0);

    // Variables to keep track of the person with the highest vote count
    let maxCount = 0;
    let maxCountPerson = 0;

    // Iterate through the persons array to determine the top voted person at each timestamp
    for (let i = 0; i < persons.length; i++) {
        // Increment the vote count for the current person
        freq[persons[i]]++;

        // Update the leading candidate if necessary
        if (freq[persons[i]] >= maxCount) {
            maxCount = freq[persons[i]];
            maxCountPerson = persons[i];
        }

        // Store the leading candidate for the current timestamp
        this.maxFreqPersons.push(maxCountPerson);
    }
};

/** 
 * @param {number} t - The query timestamp
 * @return {number} - The most voted person at time ≤ t
 */
TopVotedCandidate.prototype.q = function(t) {
    // Initialize binary search boundaries
    let low = 0, high = this.times.length - 1, idx = -1;

    // Perform binary search to find the largest time ≤ t
    while (low <= high) {
        // Find the middle index of the current search space
        let mid = Math.floor((low + high) / 2);

        // If times[mid] is within the query limit, update idx and search further in the right half
        if (this.times[mid] <= t) {
            idx = mid;
            low = mid + 1;
        } 
        // If times[mid] is greater than t, search in the left half
        else {
            high = mid - 1;
        }
    }

    // Return the most voted person at the found index, or 0 if no valid index exists
    return idx === -1 ? 0 : this.maxFreqPersons[idx];
};

Online Election Complexity Analysis

Time Complexity: O(n + qlogn)

1. Constructor Complexity (TopVotedCandidate)Breaking Down the Steps

  1. Storing persons and times in class variables → O(n)
  2. Initializing freq hashmap → O(1) (empty hashmap setup)
  3. Iterating through persons array → O(n)
    • Updating freq[persons[i]] → O(1)
    • Comparing and updating maxCount and maxCountPerson → O(1)
    • Storing maxCountPerson in maxFreqPersons → O(1)

Overall Complexity of the Constructor

Since we iterate through the persons array once and perform constant-time operations at each step, the total complexity of the constructor is: O(n)

2. Query Function Complexity (q(int t))

Breaking Down the Steps

  1. Initializing low, high, and idx → O(1)
  2. Searching for the largest times[i]t
    • Since times[] is sorted, we perform an efficient search instead of a linear scan.
    • This reduces the time complexity to O(log n) instead of O(n).
  3. Returning maxFreqPersons[idx] → O(1)

Overall Complexity of the Query Function

Since we perform a logarithmic search in times[], the total complexity of each query is: O(log⁡n)

3. Overall Complexity Analysis

If there are q queries, the total time complexity of the program is:

  • Constructor: O(n) (runs once)
  • Each Query: O(log⁡n)
  • Total for q Queries: O(qlog⁡n)

Thus, the final time complexity of the solution is: O(n+qlog⁡n)

Space Complexity: O(n)

Auxiliary Space Complexity (Extra Memory Used)

Breaking Down the Memory Usage

  1. maxFreqPersons Array:
    • Stores the leading candidate at each time index.
    • Size = n.
    • Space Used: O(n).
  2. freq HashMap/Array:
    • Stores the frequency of votes for each candidate.
    • Since persons[i] values are limited (small integer values), in the worst case, we assume they are distinct.
    • Space Used: O(n).
  3. Other Variables (maxCount, maxCountPerson, low, high, idx, mid)
    • A few integer variables.
    • Space Used: O(1).

Total Auxiliary Space Complexity

Since we use O(n) + O(n) = O(n) additional space, the auxiliary space complexity is: O(n)

Total Space Complexity (Including Input Storage)

Breaking Down the Total Memory Usage

  1. times Array:
    • Stores n time values.
    • Space Used: O(n).
  2. persons Array (Input Argument, Not Stored in Class)
    • Since persons is only used to construct maxFreqPersons, and we don’t store it explicitly, we don’t count it as additional space.
  3. Additional Storage from Auxiliary Space:
    • maxFreqPersons: O(n).
    • freq HashMap: O(n).

Total Space Complexity

Adding all components together: O(n)+O(n)=O(n)

Thus, the total space complexity is: O(n)

Similar Questions

Now we have successfully tackled this problem, let's try these similar problems:-

In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.