Watch 10 video solutions for Majority Element II, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by take U forward has 437,680 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3] Output: [3]
Example 2:
Input: nums = [1] Output: [1]
Example 3:
Input: nums = [1,2] Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
Problem Overview: Given an integer array, return all elements that appear more than ān/3ā times. Unlike the classic majority element problem, there can be at most two such numbers. Your goal is to identify those candidates efficiently.
Approach 1: HashMap Counting Technique (O(n) time, O(n) space)
The straightforward solution counts frequencies using a hash table. Iterate through the array and increment the count for each value. Once the counts are built, iterate over the map and collect elements whose frequency exceeds n/3. This approach works for any distribution of values and is easy to implement. The tradeoff is extra memory because the hash map may store up to n keys in the worst case.
Hash maps are a common pattern when solving frequency-based problems on an array. Every insertion and lookup is O(1) on average, which keeps the overall runtime linear. This solution is reliable during interviews when clarity matters more than strict space optimization.
Approach 2: Boyer-Moore Voting Algorithm Extension (O(n) time, O(1) space)
The optimal solution extends the Boyer-Moore majority voting algorithm. Since an element must appear more than n/3 times, there can be at most two valid candidates. Maintain two candidate variables and two counters. Iterate through the array and update counters based on matches or empty slots. If the current number matches a candidate, increment its count. If a counter reaches zero, replace that candidate with the current value. Otherwise, decrement both counters.
After the first pass, the two candidates are potential majority elements. Perform a second pass to verify their actual frequencies. Only return those whose count exceeds n/3. This technique works because frequent elements cancel out less frequent ones during the voting process. It achieves O(n) time and O(1) space without storing frequencies.
Recommended for interviews: Interviewers usually expect the Boyer-Moore extension because it demonstrates strong algorithmic insight and constant space optimization. The hash map solution still shows correct reasoning and understanding of counting patterns, but the voting algorithm proves you can recognize deeper constraints in the problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting | O(n) | O(n) | General case when simplicity and clarity are preferred |
| Sorting + Scan | O(n log n) | O(1) or O(log n) | Useful if the array is already sorted or sorting is acceptable |
| Boyer-Moore Voting Extension | O(n) | O(1) | Best choice for interviews and memory-constrained environments |