# Majority Element II LeetCode Solution | Easy Approach

Share:

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`

Time: O(n)
Space: O(1)

### C++

``````class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> ans;
int candidate1 = 0;
int candidate2 = 1;   // any number different from candidate1
int countSoFar1 = 0;  // # of candidate1 so far
int countSoFar2 = 0;  // # of candidate2 so far

for (const int num : nums)
if (num == candidate1) {
++countSoFar1;
} else if (num == candidate2) {
++countSoFar2;
} else if (countSoFar1 == 0) {  // assign new candidate
candidate1 = num;
++countSoFar1;
} else if (countSoFar2 == 0) {  // assign new candidate
candidate2 = num;
++countSoFar2;
} else {  // meet a new number, so pair out previous counts
--countSoFar1;
--countSoFar2;
}

const int count1 = count(begin(nums), end(nums), candidate1);
const int count2 = count(begin(nums), end(nums), candidate2);

if (count1 > nums.size() / 3)
ans.push_back(candidate1);
if (count2 > nums.size() / 3)
ans.push_back(candidate2);
return ans;
}
};``````

### Java

``````
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<>();
int candidate1 = 0;
int candidate2 = 1;  // any number different from candidate1
int countSoFar1 = 0; // # of candidate1 so far
int countSoFar2 = 0; // # of candidate2 so far

for (final int num : nums)
if (num == candidate1) {
++countSoFar1;
} else if (num == candidate2) {
++countSoFar2;
} else if (countSoFar1 == 0) { // assign new candidate
candidate1 = num;
++countSoFar1;
} else if (countSoFar2 == 0) { // assign new candidate
candidate2 = num;
++countSoFar2;
} else { // meet a new number, so pair out previous counts
--countSoFar1;
--countSoFar2;
}

int count1 = 0;
int count2 = 0;

for (final int num : nums)
if (num == candidate1)
++count1;
else if (num == candidate2)
++count2;

if (count1 > nums.length / 3)
if (count2 > nums.length / 3)
return ans;
}
}``````

### Python

``````  class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
ans1 = 0
ans2 = 1
count1 = 0
count2 = 0

for num in nums:
if num == ans1:
count1 += 1
elif num == ans2:
count2 += 1
elif count1 == 0:
ans1 = num
count1 = 1
elif count2 == 0:
ans2 = num
count2 = 1
else:
count1 -= 1
count2 -= 1

return [ans for ans in (ans1, ans2) if nums.count(ans) > len(nums) // 3]
``````

#### Watch Tutorial

Checkout more Solutions here