Majority Element II - Solution & Explanation
Problem Statement
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?
Approach Overview
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 1: HashMap Counting Technique
This approach leverages a hashmap to count the occurrences of each element in the input array. We iterate through the array once to populate the hashmap and then make another pass to find all elements whose count is greater than ⌊n/3⌋. While this method is straightforward and simple to implement, it uses extra space proportional to the number of unique elements.
The provided C code creates a custom hashmap-like structure to count elements. This hashmap uses an array of structs where each struct holds a key-value pair corresponding to a number and its count. We iterate over the input array to update the counts, and finally check which numbers exceed the ⌊n/3⌋ threshold. Note that handling collisions could be optimized further.
Complexity
Time Complexity: O(n), where n is the length of the array since we go through the list of numbers twice.
Space Complexity: O(n) to handle the possible maximum unique elements.
Approach 2: Boyer-Moore Voting Algorithm Extension
The Boyer-Moore Voting Algorithm is optimized for finding the majority element which appears more than n/2 times. Here, we extend it to handle the case for n/3 by maintaining up to two potential candidates, since at most two elements can qualify for appearing more than ⌊n/3⌋ times. In the first pass, we identify the element candidates by attempting to cancel them out against others. A second pass is required to confirm the counts of these candidates to ensure they appear more than ⌊n/3⌋ times.
This C program applies Boyer-Moore to locate up to two potential majority elements. Initial counts start at zero, and when a candidate is different, the count decreases. If zeroed, a new candidate is established. A further check verifies that these candidates surpass ⌊n/3⌋ occurrences.
Complexity
Time Complexity: O(n), going through elements twice.
Space Complexity: O(1) as no additional space is needed apart from variables.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| HashMap Counting Technique | Time Complexity: O(n), where n is the length of the array since we go through the list of numbers twice. |
| Boyer-Moore Voting Algorithm Extension | Time Complexity: O(n), going through elements twice. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Majority Element II - Leetcode 229 - Python • NeetCodeIO • 45,805 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Majority Element II easy or hard?
How to solve Majority Element II in O(n)?
Majority Element II Python or Java solution?
What is the best approach for Majority Element II?
What data structure is used in Majority Element II?
What is the time complexity of Majority Element II?
Is Majority Element II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Majority Element II with our built-in code editor and test cases.
Practice on FleetCode