Approach: Count then filter (at most two can qualify)

def majorityElement(nums):
    n = len(nums)
    from collections import Counter
    cnt = Counter(nums)
    return sorted(v for v in cnt if cnt[v] * 3 > n)

Complexity: O(n) time, O(n) space.

Full Solution — all languages

class Solution:
    def majorityElement(self, nums):
        from collections import Counter
        n = len(nums)
        cnt = Counter(nums)
        return sorted(v for v in cnt if cnt[v] * 3 > n)

import java.util.*;
class Solution {
    public int[] majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) if (e.getValue() * 3 > n) res.add(e.getKey());
        Collections.sort(res);
        int[] r = new int[res.size()];
        for (int i = 0; i < r.length; i++) r[i] = res.get(i);
        return r;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: vector<int> majorityElement(vector<int>& nums) {
        int n = (int)nums.size();
        map<int, int> cnt;
        for (int x : nums) cnt[x]++;
        vector<int> res;
        for (auto& p : cnt) if (p.second * 3 > n) res.push_back(p.first);
        sort(res.begin(), res.end());
        return res;
    }
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */ var majorityElement = function(nums) {
    const n = nums.length;
    const cnt = new Map();
    for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
    const res = [];
    for (const [k, v] of cnt) if (v * 3 > n) res.push(k);
    res.sort((a, b) => a - b);
    return res;
};

Majority Element II

Example 1

Example 2

Example 3

Constraints