algoadvance

Leetcode 911. Online Election

Problem Statement

The problem “911. Online Election” on LeetCode can be summarized as follows:

You have been given two arrays, persons and times. The persons[i] represents the person that was voted for at time times[i].

Implement the TopVotedCandidate class with the following methods:

• 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.

Clarifying Questions

1. What if the times array contains duplicate values?
   • For this problem, it’s implied that times is strictly increasing and contains unique values.
2. How large can the arrays be?
   • According to the problem constraints, the size of persons and times can be up to 5000.
3. What should be returned if t is earlier than the first vote time?
   • It’s safe to assume that such scenarios won’t be queried according to the problem constraints.

Strategy

1. Creating a Lead Tracking System:
   • We need to track the leading candidate at each timestamp up to the given query time t.
2. Precompute Leading Candidates:
   • We can iterate through the persons array and maintain a count of votes for each candidate.
   • As we iterate, keep track of the current leading candidate.
   • Store the leading candidate at each time in a list.
3. Efficient Query Handling:
   • Precompute the results for all times in the given times array.
   • For each query q(t), perform a binary search to find the largest time <= t and return the leading candidate at that time.

Code

import java.util.*;

class TopVotedCandidate {
    private Map<Integer, Integer> leadingCandidates;
    private int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.leadingCandidates = new HashMap<>();
        Map<Integer, Integer> voteCounts = new HashMap<>();
        
        int leadingCandidate = -1;
        int maxVotes = 0;
        
        for (int i = 0; i < persons.length; i++) {
            int person = persons[i];
            int time = times[i];
            
            voteCounts.put(person, voteCounts.getOrDefault(person, 0) + 1);
            if (voteCounts.get(person) >= maxVotes) {
                if (voteCounts.get(person) > maxVotes || person != leadingCandidate) {
                    leadingCandidate = person;
                    maxVotes = voteCounts.get(person);
                }
            }
            leadingCandidates.put(time, leadingCandidate);
        }
    }
    
    public int q(int t) {
        int left = 0, right = times.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (times[mid] <= t) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return leadingCandidates.get(times[right]);
    }
}

Time Complexity

• Initialization (Constructor): O(N), where N is the number of votes. This is because we make a single pass through the persons and times arrays and update the HashMaps.
• Querying (q(int t)): O(log N) per query due to the binary search on the times array.

This approach ensures efficient precomputation and quick query responses, making the class suitable for handling up to 5000 votes gracefully.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?