229. Majority Element II - Leetcode

Problem

Problem Link

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.

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)