## DEV Community is a community of 851,150 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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>();

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.