# Majority Element II

## Problem

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

{% hint style="info" %}
Example:

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

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

{% endhint %}

### Thought Process

* **Moore's Voting Algorithm**: We have to use Moore's Voting Algorithm so we can find the potential candidates. Since Moore's Voting Algorithm finds the majority element in a sequence, this is perfect for finding the candidates that may appear more than `⌊ n/3 ⌋` times. In this case, there are **two** potential candidates.

* The reason why we can have 2 possible majority elements at max is because the problem asks us to **find all elements that appear more than `⌊ n/3 ⌋` times.** Suppose there are three elements that appeared more than `⌊ n/3 ⌋` times, then there needs to be at least $$3  \* ⌊ n/3 + 1 ⌋> n$$ elements in the array, which is not possible ( $$(n/3+1)+(n/3+1)+(n/3+1) > n)$$ . 

  * e.g. suppose $$n = 9$$, then the problem asks to find all elements that appeared more than 3 times, which means they have to appear at least 4 times. There can't be 3 items in the array of length 9 that all have appeared 4 times. 

   

* Similar to **Majority Element I**, we will use Moore's Voting Algorithm to find two potential candidates to be later verified that they occur more than `⌊ n/3 ⌋` times.

## Solution

```
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
   
        candA, countA = 0,0
        candB, countB = 0,0
        
        for n in nums:
            if candA == n:
                countA += 1
            elif candB == n:
                countB += 1
            elif countA == 0:
                candA = n
                countA = 1
            elif countB == 0:
                candB = n
                countB = 1
            else:
                countA-=1
                countB-=1
 

        countA = countB = 0
        for n in nums:
            if candA == n:
                countA += 1
            elif candB == n:
                countB += 1
        
        res = []
        if countA > len(nums) // 3:
            res.append(candA)
        if countB > len(nums) // 3:
            res.append(candB)
            
        return res
```

## Key Facts

* We are using **Moore's Voting Algorithm** to find majority elements so that we can later verify that these elements occure more than`⌊ n/3 ⌋` times. Moore's Voting Algorithm gives us **potential** candidates since it will find elements that occur the most. We have to then verify these elements.

* The reason why we can have two majority elements at **max** is because for finding $$1/k$$ majority,  $$k-1$$elements can qualify.

## Time Complexity

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