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] <= 109Follow up: Could you solve the problem in linear time and in O(1) space?
The key insight for Majority Element II is that an element must appear more than n/3 times in the array. At most, there can be only two such elements. A highly efficient approach uses a modified Boyer–Moore Voting Algorithm. Instead of tracking one candidate, it tracks two potential candidates and their counts while iterating through the array. After this pass, a second verification pass confirms whether the candidates actually appear more than n/3 times.
Alternative approaches include using a hash table to count frequencies or sorting the array and scanning for repeated values. While these methods are easier to reason about, they may require extra space or additional time for sorting.
The Boyer–Moore variation is the most optimal since it runs in linear time and uses constant extra space, making it ideal for large input sizes commonly seen in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Boyer–Moore Voting (n/3 variant) | O(n) | O(1) |
| Hash Map Counting | O(n) | O(n) |
| Sorting + Scan | O(n log n) | O(1) or O(log n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Think about the possible number of elements that can appear more than ⌊ n/3 ⌋ times in the array.
It can be at most two. Why?
Consider using Boyer-Moore Voting Algorithm, which is efficient for finding elements that appear more than a certain threshold.
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.
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.
1import java.util.*;
2
3public class MajorityElement {
4 public List<Integer> majorityElement(int[] nums) {
This Java solution uses a HashMap to count the frequency of each element in the input array. We iterate over the array to populate the map. Once the map is filled, we iterate over its entries to collect keys (numbers) having values (counts) greater than ⌊n/3⌋. The HashMap enables efficient storage and lookup of key-value pairs.
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.
Time Complexity: O(n), going through elements twice.
Space Complexity: O(1) as no additional space is needed apart from variables.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Majority Element II problem frequently appear in technical interviews at top companies. It tests knowledge of array traversal, frequency counting, and optimized algorithms like the Boyer–Moore voting technique.
A hash table is the most straightforward structure for counting frequencies of elements. However, the Boyer–Moore voting approach avoids extra storage and is typically preferred in interviews due to its constant space usage.
The optimal solution uses a modified Boyer–Moore Voting Algorithm that tracks up to two candidates because at most two elements can appear more than n/3 times. It runs in O(n) time and uses O(1) extra space, followed by a verification pass to confirm the candidates.
If an element must appear more than n/3 times, three such elements would require more than n total occurrences. This mathematical constraint ensures that only two elements can satisfy the condition in any array.
This JavaScript solution applies Boyer-Moore for one-pass candidate identification and another for finalizing counts, ensuring candidates exceeding ⌊n/3⌋ are validated and returned.