> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/array/medium/229.-majority-element-ii.md).

# 229. Majority Element II

## Problem Statement

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

 

**Example 1:**

<pre><code><strong>Input: nums = [3,2,3]
</strong><strong>Output: [3]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1]
</strong><strong>Output: [1]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [1,2]
</strong><strong>Output: [1,2]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `-109 <= nums[i] <= 109`

&#x20;

**Follow up:** Could you solve the problem in linear time and in `O(1)` space?

## Intuition

```
Basically:

In Moore Voting for n/2 
For every second element we pop
XXXXYYY
For Every X we pop Y

But here there is XYZ for n/3
For every Z we pop X and Y

Hence in last else we pop or reduce Count1 and count2 for a different element

Edge case el1 and el2 can become same hence
we check el2 != it


At end we check count for elements again
1 2 3) 4 5 6) 7 8

In the end 7 and 8 remains but not answer
```

### Links

<https://leetcode.com/problems/majority-element-ii/description/>

### Video Links

<https://www.youtube.com/watch?v=Eua-UrQ_ANo&ab_channel=NeetCodeIO>\
<https://www.youtube.com/watch?v=vwZj1K0e9U8&t=1535s&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int el1, el2, count1=0, count2=0;
        for(auto &it: nums){
            if(count1 == 0 and el2 != it){
                el1 = it;
                count1=1;
            }
            else if(count2 == 0 and el1 != it){
                el2 = it;
                count2=1;
            }
            else if(el1 == it)
                count1++;
            else if(el2 == it)
                count2++;
            else{
                count1--;   count2--;
            }
        }
        
        vector<int> ans;
        int ct1=0, ct2=0;
        for(auto &it: nums){
            if(el1 == it)
                ct1++;
            if(el2 == it)
                ct2++;
        }

        int idx = nums.size()/3 +1;
        if(ct1 >= idx)
            ans.push_back(el1);
        if(ct2 >= idx)
            ans.push_back(el2);

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###