Striver's SDE Sheet Journey - #16 Majority Element (>N/3 times)

Problem Statement :-

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example

Input : nums = [3,2,3]

Result : 3

Solution 1

in this solution, we just need to find the two most frequent elements in the array nums and count the frequency of the frequent elements if the count is greater than N/3 then return the elements.

let's discuss this approach step by step.

step-1 declare some variables.
firstMajNum = null
secondMajNum = null
firstMajCount = 0
secondMajCount = 0

firstMajNum & secondMajNum will store the currently most frequent elements.

_firstMajCount & secondMajCount will store the frequency of the current most frequent element._

step-2 run a loop from i=0 to n.

1. get the ith element from array nums.
element = nums[i]

2. increase the firstMajCount if element == firstMajNum

3. increase the secondMajCount if element == secondMajNum

4. declare firstMajCount & firstMajNum if firstMajCount == 0.

firstMajCount = 1
firstMajNum = element

5. declare secondMajCount & secondMajNum if secondMajCount == 0

secondMajCount = 1
secondMajNum = element

6. if all the above cases not satisfy, decrease the secondMajCount & secondMajCount by 1

step-3 count the frequency of the most frequent elements of the array & return those elements that are >N/3.

see the java implementation.

Java

class Solution {
    public List<Integer> majorityElement(int[] nums) {

        Integer firstMajNum = null;
        Integer secondMajNum = null;
        int firstMajCount = 0;
        int secondMajCount = 0;


        for(int i=0; i<nums.length; i++){

            int element = nums[i];

            if(firstMajNum != null && element == firstMajNum){       
                firstMajCount++;

            }else if (secondMajNum != null && element == secondMajNum){   
                secondMajCount++;

            }else if(firstMajCount == 0){
                firstMajNum = element;
                firstMajCount = 1;

            }else if(secondMajCount == 0){
                secondMajNum = element;
                secondMajCount = 1;
            }else{
                firstMajCount--;
                secondMajCount--;

                if(firstMajCount == 0) firstMajNum = null;
                if(secondMajCount == 0) secondMajNum = null;
            }
        }

         firstMajCount = 0;
         secondMajCount = 0;

        for(int e : nums){
           if(firstMajNum != null && firstMajNum == e) firstMajCount++;

            if(secondMajNum != null && secondMajNum == e) secondMajCount++;
        }

        List<Integer> ans = new ArrayList<Integer>();

        if(firstMajCount > nums.length/3) ans.add(firstMajNum);
        if(secondMajCount > nums.length/3) ans.add(secondMajNum);


        return ans;

    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Thank you for reading this article i hope you like and plz share with your dev friends. if you find something wrong let me in the comment section.