> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/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. The algorithm should run in linear time and in O(1) space.

```cpp
vector<int> majorityElement(vector<int> &elements) 
{
    int n_over_3 = elements.size() / 3;

    unordered_map<int,int> int_freq;
    for (int i = 0; i < elements.size(); i++) {
        if (int_freq.find(elements.at(i)) != int_freq.end()) {
            int_freq[elements.at(i)]++;
        }
        else {
            int_freq.insert(make_pair(elements.at(i), 1));
        }
    }

    vector<int> majority_elements;
    for (auto i : int_freq) {
        if (i.second > n_over_3) {
            majority_elements.push_back(i.first);
        }
    }

    return majority_elements;
}
```