Majority Element II
Understanding the Problem
This is a generalization of the classic Majority Element problem (LeetCode 169), where we needed to find the element appearing more than n/2 times. That problem guaranteed exactly one answer. Here, we need to find all elements appearing more than n/3 times.
A mathematical constraint bounds the answer: at most two elements can appear more than n/3 times. If three elements each appeared more than n/3 times, that would account for more than n total elements, which is impossible. So the answer list has at most 2 elements.
This bound shapes every approach. The hash map counts every element and filters, sorting groups equal values into runs, and the Boyer-Moore approach exploits the "at most 2 candidates" fact to run in constant space.
Key Constraints:
1 <= nums.length <= 5 * 10^4→ With n up to 50,000, O(n^2) means 2.5 billion operations, which is too slow. We need O(n log n) or better.-10^9 <= nums[i] <= 10^9→ Values span the full 32-bit integer range, so we can't use array indexing for counting. We need a hash map or a comparison-based approach.- The follow-up explicitly asks for O(n) time and O(1) space, hinting at the Boyer-Moore Voting algorithm.
Approach 1: Hash Map Counting
Intuition
Count how many times each element appears, then check which counts exceed n/3. A hash map gives O(1) average lookups and insertions, so the counting takes a single pass, and a second pass over the distinct keys filters out the elements above the threshold.
Algorithm
- Create a hash map to store the count of each element.
- Iterate through
nums, incrementing the count for each element. - Calculate the threshold as
n / 3. - Iterate through the hash map entries, collecting elements whose count exceeds the threshold.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once to build the count map, and once more through the map entries. Both passes are O(n).
- Space Complexity: O(n). In the worst case (all unique elements), the hash map stores n entries.
This is correct but uses O(n) extra space for the count map. The next approach removes that auxiliary space at the cost of a slower runtime.
Approach 2: Sorting
Intuition
After sorting, all occurrences of the same element become adjacent. An element that appears more than n/3 times occupies a contiguous run longer than n/3. So one scan over the sorted array, measuring each run's length and comparing it against the threshold, finds every majority element.
This trades the O(n) space of a hash map for the O(n log n) time of sorting, and it modifies the input.
Algorithm
- Sort the array.
- Initialize a counter and iterate through the sorted array.
- For each new value, count its consecutive occurrences.
- If the count exceeds
n/3, add it to the result. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The subsequent linear scan is O(n), so sorting dominates.
- Space Complexity: O(1). We use only a few variables. Some sorting algorithms use O(log n) stack space, but no auxiliary data structures.
Sorting still costs O(n log n). The final approach finds the candidates in linear time and constant space, satisfying the follow-up.
Approach 3: Boyer-Moore Voting (Optimal)
Intuition
This extends the Boyer-Moore Majority Vote algorithm. The original finds the element appearing more than n/2 times using one candidate and one counter. For the n/3 threshold, it uses two candidates and two counters.
The mechanism is cancellation. When an element matches neither candidate and both counters are non-zero, the algorithm decrements both counters, discarding one occurrence of each candidate along with the current element. Three distinct elements remove each other from contention. After the first pass, the two surviving candidates are the only possible answers, but survival alone does not prove either exceeds n/3, so a second pass counts their true frequencies.
Each cancellation step removes three distinct values at once: the current element and one tallied occurrence of each candidate. An element that appears count times can therefore lose at most one tallied occurrence per cancellation, and each cancellation also consumes a value not equal to it. The most cancellations possible is (n - count) / 2, since every cancellation pairs the element against two other distinct values. When count > n/3, that bound is below count, so the element keeps a positive tally and ends as one of the two candidates.
The converse does not hold. A candidate can survive the first pass without appearing more than n/3 times, for example when no true majority element exists. The second pass that recounts both candidates is therefore required.
Algorithm
- Initialize two candidates (
cand1,cand2) and their counts (count1 = 0,count2 = 0). - First pass (find candidates): iterate through
nums: - If
num == cand1, incrementcount1. - Else if
num == cand2, incrementcount2. - Else if
count1 == 0, setcand1 = numandcount1 = 1. - Else if
count2 == 0, setcand2 = numandcount2 = 1. - Else decrement both
count1andcount2. - Second pass (verify candidates): count the actual occurrences of
cand1andcand2. - Add to result any candidate whose count exceeds
n/3.
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the array, each O(n). Total is O(2n) = O(n).
- Space Complexity: O(1). Only uses a fixed number of variables: two candidates, two counters, and the result list.