229. Majority Element II - Leetcode


Problem
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]
Moore's Voting Algorithm Visualization - Link
Dictionary or Map approach
This approach will count how many times each value in the given array of integer numbers repeats. It will iterate through the keys in the map and store those with a frequency greater than n/3 in a list.
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
Map<Integer, Integer> freqMap = new HashMap<>();
for(int key: nums){
if(!freqMap.containsKey(key)){
freqMap.put(key, 0);
}
int val = freqMap.get(key);
freqMap.put(key, val+1);
}
List<Integer> ans = new ArrayList<>();
for(int key: freqMap.keySet()){
int value = freqMap.get(key);
if(value>n/3)
ans.add(key);
}
return ans;
}
}
Time Complexity: O(n) (Assuming the hashmap retrieval is constant)
Space Complexity: O(n)
Extension of Moore's Voting Algorithm
Base scenario
[2, 2, 2, 3, 3, 3, 1, 1, 1]
In this scenario, there is no majority element because all the elements occupy 1/3rd of the total members. Therefore, intuition builds up from here. The maximum number of majority elements possible is 2. Another way to look at it is that the maximum number of possible elements with an n/3 frequency is 3.
Intuition Extension from Moore's Algorithm
Here distinct elements indicate different armies. In the above scenario, there are 3 armies and each army has a strength of 3.
Army | Total Members |
2 | 3 |
3 | 3 |
1 | 3 |
To form two majority armies, the majority armies must maintain friendly relations with each other to avoid internal conflicts. The key constraint is that these two majority armies can each eliminate only one non-majority soldier, resulting in the death of all three soldiers from three different armies. This restriction is crucial to the strategy of creating two majority armies.
Moore's execution example
[2,1,3,2,4,1,2,2,1]
2 and 1 will eliminate 3 and be eliminated themselves.
2 and 4 will eliminate 1 and be eliminated themselves.
The remaining elements, 2 and 1, are the majority elements left.
Code
Here, we assume there are two elements that constitute the majority armies. We increase or decrease the count based on the encounter. Before assigning a new element as the majority army, we perform a mandatory check when the count reaches 0. This is done to ensure that both majority armies do not point to a single element. Initially, we initialize both armies to nums[0], but these values will be overridden when the count reaches 0 as the for loop progresses.
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
int count1 = 0;
int count2 = 0;
int army1 = nums[0];
int army2 = nums[0];
for(int i=0; i<n; i++){
if(count1==0 && nums[i]!=army2){
army1=nums[i];
count1+=1;
}
else if(count2==0 && nums[i]!=army1){
army2=nums[i];
count2+=1;
}
else if(army1==nums[i]) count1+=1;
else if(army2==nums[i]) count2+=1;
else{
count1-=1;
count2-=1;
}
}
//Verification
List<Integer> ans = new ArrayList<>();
count1=0;
count2=0;
for(int i=0; i<n; i++){
if(nums[i]==army1) count1+=1;
else if(nums[i]==army2) count2+=1;
}
if(count1>n/3)
ans.add(army1);
if(count2>n/3)
ans.add(army2);
return ans;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
Subscribe to my newsletter
Read articles from Chetan Datta directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Chetan Datta
Chetan Datta
I'm someone deeply engrossed in the world of software developement, and I find joy in sharing my thoughts and insights on various topics. You can explore my exclusive content here, where I meticulously document all things tech-related that spark my curiosity. Stay connected for my latest discoveries and observations.