Watch 10 video solutions for Majority Element II, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by take U forward has 435,139 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 nums, return all elements that appear more than ⌊n/3⌋ times. Unlike the classic majority element problem (n/2), this variant can have at most two valid answers because three distinct numbers appearing more than n/3 times would exceed the array length.
Approach 1: HashMap Counting Technique (O(n) time, O(n) space)
This method directly counts the frequency of every element using a hash map. Iterate through the array and increment the count for each number with a constant-time hash lookup. After building the frequency table, iterate over the map and collect keys whose counts exceed ⌊n/3⌋. The approach is straightforward and works for any distribution of numbers because it explicitly tracks counts.
This solution relies on a hash table for fast insert and lookup operations. It runs in O(n) time since each element is processed once, but it requires O(n) extra space to store frequencies. You would typically use this approach when clarity and quick implementation matter more than memory optimization.
Approach 2: Boyer-Moore Voting Algorithm Extension (O(n) time, O(1) space)
The optimal solution extends the Boyer-Moore majority vote algorithm. Because at most two elements can appear more than n/3 times, maintain two candidate values and their counters. Iterate through the array and update counters using a cancellation principle: matching numbers increment the corresponding counter, empty counters adopt a new candidate, and mismatches decrement both counters.
After the first pass, the candidates are potential majority elements but not guaranteed. Run a second pass through the array to verify their actual counts and include only those exceeding ⌊n/3⌋. This algorithm works because non-majority elements cancel each other out during the voting process. The result is O(n) time with only O(1) additional memory, making it extremely efficient for large inputs.
Recommended for interviews: Interviewers usually expect the Boyer-Moore extension. The hash map approach shows you understand frequency counting with a counting strategy, but the optimal solution demonstrates deeper algorithmic reasoning and space optimization. Start with the counting idea if needed, then refine it to the constant-space voting technique.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting Technique | O(n) | O(n) | Best for quick implementation or when extra memory is not a concern. |
| Boyer-Moore Voting Algorithm Extension | O(n) | O(1) | Preferred in interviews and memory-constrained environments. |