algoadvance

Leetcode 911. Online Election

Problem Statement

The problem “911. Online Election” from Leetcode states the following:

You are given two arrays persons and times. The persons array contains the candidates’ IDs who have received votes in chronological order, and times array contains the corresponding times at which these votes were cast.

In this problem, we need to initialize an object with these arrays. We are then given the task to implement a function q(t) that returns the ID of the candidate that was leading the election at time t.

Clarifying Questions

  1. Can two candidates have the same number of votes at any given time?
    • Yes, and in such a case, the most recent candidate to reach that vote count would be considered leading.
  2. Do we handle only queries that use exact timestamps in the times array, or can t be any time between the elements in times?
    • t can be any time, not necessarily in the times array; thus, we must find the leading candidate at or just before time t.
  3. Are all inputs valid and within constraints as specified?
    • Yes, assume all inputs are valid and the constraints will be met.

Strategy

To solve this problem, we will:

  1. Use a map to keep track of the current votes for each candidate.
  2. Use a vector to keep track of the leader at each time in times.
  3. Use binary search for efficient time querying.

Steps:

  1. Iterate through the persons and times arrays simultaneously to maintain a record of who the current leader is after each vote.
  2. Use a dictionary to maintain the count of votes for each candidate.
  3. Update a list of leaders whenever there is a change in the leader.
  4. To answer the query q(t), use binary search to find the closest time less than or equal to t and return the recorded leader at that time.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <map>

class TopVotedCandidate {
private:
    std::vector<int> times;
    std::vector<int> leaders;

public:
    TopVotedCandidate(std::vector<int>& persons, std::vector<int>& times) {
        this->times = times;
        std::unordered_map<int, int> voteCounts;
        int leader = -1;
        int leaderVotes = 0;

        for (int i = 0; i < persons.size(); ++i) {
            voteCounts[persons[i]]++;
            if (voteCounts[persons[i]] >= leaderVotes) {
                if (leader == -1 || persons[i] != leader || voteCounts[persons[i]] > leaderVotes) {
                    leader = persons[i];
                    leaderVotes = voteCounts[persons[i]];
                }
            }
            leaders.push_back(leader);
        }
    }
    
    int q(int t) {
        int idx = std::upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return leaders[idx];
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */

Time Complexity

  1. Initialization (TopVotedCandidate constructor): The constructor processes each vote once, so it runs in O(N) time where N is the number of votes.
  2. Query (q function): Each query uses binary search which has a time complexity of O(log N).

Thus, the overall complexity is efficient for both initialization and querying, making this approach suitable for handling large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI