# 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)$$ 


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/repeat-missing-numbers/majority-element-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.