Striver's SDE Sheet Journey - #16 Majority Element (>N/3 times)
Tags: programming, beginners, computerscience, java
Published: 2022-01-21 09:01:26

> **<u>Problem Statement</u> :-**

_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`


##  <u>Solution 1</u>
_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

```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.