# 229. Majority Element II | LeetCode Solution

## 229. Majority Element II

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

Example 1:

```Input: nums = [3,2,3]
Output: [3]
```

Example 2:

```Input: nums = [1]
Output: [1]
```

Example 3:

```Input: nums = [1,2]
Output: [1,2]
```

Constraints:

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

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

## The solution to the above question is

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n=floor(nums.size()/3);
vector<int>ans;
int num1=-1;
int num2=-1;
int cnt1=0;
int cnt2=0;
for(int i=0; i<nums.size(); i++){
if(nums[i]==num1)cnt1++;
else if(nums[i]==num2)cnt2++;
else if(cnt1==0){num1=nums[i];cnt1=1;}
else if(cnt2==0){num2=nums[i];cnt2=1;}
else{
cnt1--;
cnt2--;
}
}
int c1=0,c2=0;
for(int i=0; i<nums.size(); i++){
if(nums[i]==num1)c1++;
if(nums[i]==num2)c2++;
}
if(c1>n)ans.push_back(num1);
if(c2>n && num1!=num2)ans.push_back(num2);
return ans;
}
};