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
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(); }}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.