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.

## Discussion (0)