Majority Element II
MedPrompt
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?
Approaches
3 approaches with complexity analysis and trade-offs.
The simplest approach is to count the frequency of each element in the array and check which elements appear more than ⌊n/3⌋ times.
Algorithm
- Initialize an empty result list and a set to track processed elements
- For each element nums[i] in the array:
- If element is already processed, skip it
- Count its frequency by comparing with remaining elements
- If frequency > ⌊n/3⌋, add to result
- Add element to processed set
- Return result list
Walkthrough
For each element in the array, we count its frequency by comparing it with all other elements. If the frequency is greater than ⌊n/3⌋, we add it to our result list. To avoid duplicates, we can maintain a set of elements we've already processed.
public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<>(); Set<Integer> seen = new HashSet<>(); int n = nums.length; int threshold = n / 3; for (int i = 0; i < n; i++) { if (seen.contains(nums[i])) continue; int count = 1; for (int j = i + 1; j < n; j++) { if (nums[j] == nums[i]) { count++; } } if (count > threshold) { result.add(nums[i]); } seen.add(nums[i]); } return result;}Complexity
Time
O(n²) where n is the length of the array as we need two nested loops
Space
O(1) excluding the space used for output
Trade-offs
Pros
Simple to understand and implement
No extra space required except for output
Cons
Very inefficient for large arrays
Requires nested loops making it slow
We can use a HashMap to store the frequency of each element in a single pass through the array, then check which elements appear more than ⌊n/3⌋ times.
Algorithm
- Initialize a HashMap to store element frequencies
- Traverse array once to count frequencies
- Check HashMap entries for elements with frequency > ⌊n/3⌋
- Add qualifying elements to result list
Walkthrough
We first create a HashMap to store element-frequency pairs. We traverse the array once to count frequencies, then check which elements have frequency greater than ⌊n/3⌋.
public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<>(); Map<Integer, Integer> countMap = new HashMap<>(); int n = nums.length; int threshold = n / 3; // Count frequencies for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1); } // Check which elements appear more than n/3 times for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) { if (entry.getValue() > threshold) { result.add(entry.getValue()); } } return result;}Complexity
Time
O(n) where n is the length of the array
Space
O(n) to store the HashMap
Trade-offs
Pros
More efficient than brute force approach
Only requires single pass through array
Easy to implement and understand
Cons
Requires extra space proportional to input size
Not optimal in terms of space complexity
We can use a modified version of Boyer-Moore Majority Vote algorithm to find elements appearing more than ⌊n/3⌋ times in O(n) time and O(1) space.
Algorithm
- Initialize two candidates and their counters
- First pass: Use Boyer-Moore voting to find potential candidates
- If current number matches either candidate, increment respective counter
- If a counter is 0, replace that candidate
- If neither matches and both counters > 0, decrement both counters
- Second pass: Count actual frequencies of candidates
- Add candidates to result if they appear more than ⌊n/3⌋ times
Walkthrough
Since we're looking for elements appearing more than ⌊n/3⌋ times, there can be at most two such elements. We can use two counters and two candidates to keep track of potential majority elements.
public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<>(); if (nums == null || nums.length == 0) return result; // First pass to find candidates int candidate1 = nums[0], candidate2 = nums[0]; int count1 = 0, count2 = 0; for (int num : nums) { if (num == candidate1) { count1++; } else if (num == candidate2) { count2++; } else if (count1 == 0) { candidate1 = num; count1 = 1; } else if (count2 == 0) { candidate2 = num; count2 = 1; } else { count1--; count2--; } } // Second pass to verify candidates count1 = 0; count2 = 0; for (int num : nums) { if (num == candidate1) count1++; else if (num == candidate2) count2++; } int threshold = nums.length / 3; if (count1 > threshold) result.add(candidate1); if (count2 > threshold && candidate1 != candidate2) result.add(candidate2); return result;}Complexity
Time
O(n) where n is the length of the array
Space
O(1) as we only use a constant amount of extra space
Trade-offs
Pros
Optimal time complexity O(n)
Constant space complexity O(1)
Works in two passes through the array
Cons
More complex to understand and implement
Requires two passes through the array
Solutions
Solution
public class Solution { public IList < int > MajorityElement(int[] nums) { int n1 = 0, n2 = 0; int m1 = 0, m2 = 1; foreach(int m in nums) { if (m == m1) { ++n1; } else if (m == m2) { ++n2; } else if (n1 == 0) { m1 = m; ++n1; } else if (n2 == 0) { m2 = m; ++n2; } else { --n1; --n2; } } var ans = new List < int > (); ans.Add(m1); ans.Add(m2); return ans.Where(m => nums.Count(n => n == m) > nums.Length / 3).ToList(); }}class Solution {public List<Integer> majorityElement(int[] nums) { int n1 = 0, n2 = 0; int m1 = 0, m2 = 1; for (int m : nums) { if (m == m1) { ++n1; } else if (m == m2) { ++n2; } else if (n1 == 0) { m1 = m; ++n1; } else if (n2 == 0) { m2 = m; ++n2; } else { --n1; --n2; } } List<Integer> ans = new ArrayList<>(); n1 = 0; n2 = 0; for (int m : nums) { if (m == m1) { ++n1; } else if (m == m2) { ++n2; } } if (n1 > nums.length / 3) { ans.add(m1); } if (n2 > nums.length / 3) { ans.add(m2); } return ans; }}class Solution {public: vector<int> majorityElement(vector<int> &nums) { int n1 = 0, n2 = 0; int m1 = 0, m2 = 1; for (int m : nums) { if (m == m1) ++n1; else if (m == m2) ++n2; else if (n1 == 0) { m1 = m; ++n1; } else if (n2 == 0) { m2 = m; ++n2; } else { --n1; --n2; } } vector<int> ans; if (count(nums.begin(), nums.end(), m1) > nums.size() / 3) ans.push_back(m1); if (count(nums.begin(), nums.end(), m2) > nums.size() / 3) ans.push_back(m2); return ans; }};class Solution: def majorityElement(self, nums: List[int]) -> List[int]: n1 = n2 = 0 m1, m2 = 0, 1 for m in nums: if m == m1: n1 += 1 elif m == m2: n2 += 1 elif n1 == 0: m1, n1 = m, 1 elif n2 == 0: m2, n2 = m, 1 else: n1, n2 = n1 - 1, n2 - 1 return [m for m in [m1, m2] if nums . count(m) > len(nums) // 3]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.