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

# 229. Majority Element II

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

**Note:** The algorithm should run in linear time and in O(1) space.

**Example 1:**

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

**Example 2:**

```
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
```

```cpp
// Moore Voting Method
vector<int> majorityElement(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size(), cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
    vector<int> res;
    for (int num : nums) {
        if (num == cand1) ++cnt1;
        else if (num == cand2) ++cnt2;
        else if (cnt1 == 0) {
            cand1 = num;
            ++cnt1;
        } else if (cnt2 == 0) {
            cand2 = num;
            ++cnt2;
        } else {
            --cnt1, --cnt2;
        }
    }
    // Reset counters
    cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
        if (num == cand1) ++cnt1;
        else if (num == cand2) ++cnt2;
    }
    if (cnt1 > n / 3) res.push_back(cand1);
    if (cnt2 > n / 3) res.push_back(cand2);
    return res;
}
```

{% content-ref url="/pages/-LbRsr7\_uJ5DPkEglBp5" %}
[169. Majority Element](/practice-of-algorithm-problems/array/169.-majority-element.md)
{% endcontent-ref %}