Majority Element II — Solution in Python, Java & C++
Majority Element II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Majority Element II is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Counting
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums of size n, return every element that appears more than n / 3 times, in increasing order.
At most two such elements can exist.
Example 1
Input: nums = [3,2,3]
Output: [3]
Explanation: 3 appears twice out of three, and 2 > 3/3.
Example 2
Input: nums = [1]
Output: [1]
Example 3
Input: nums = [1,2]
Output: [1,2]
Explanation: Each appears once, and 1 > 2/3.
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000
Follow-up: Can you do it in O(n) time and O(1) space? (Boyer–Moore generalises to two candidates.)
Hints for Majority Element II
Hint 1
Counting occurrences in a hash map and filtering by the
n / 3threshold is the direct O(n) solution.Hint 2
Use a strict
>comparison — exactlyn / 3occurrences does not qualify.Hint 3
The O(1)-space version keeps two candidates with two counters, then verifies both in a second pass.
How to solve Majority Element II
Count every value and keep those whose count strictly exceeds n / 3; at most two can qualify.
Approach
- Tally occurrences in a map.
- Filter values with
count > n / 3. - Sort and return.
Why it works
Three values each appearing more than n / 3 times would total more than n elements, so the filter yields at most two.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Use a strict comparison; exactly
n / 3occurrences does not qualify. - Boyer–Moore with two candidates plus a verification pass gives O(1) space.
Reference solution
Python
def majorityElement(nums):
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
threshold = len(nums) / 3
return sorted(v for v, c in count.items() if c > threshold)Java
public static int[] majorityElement(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
List<Integer> out = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : count.entrySet()) {
if (e.getValue() * 3 > nums.length) out.add(e.getKey());
}
Collections.sort(out);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> count;
for (int x : nums) count[x]++;
vector<int> out;
for (auto& kv : count) {
if (kv.second * 3 > (int) nums.size()) out.push_back(kv.first);
}
sort(out.begin(), out.end());
return out;
}JavaScript
var majorityElement = function(nums) {
const count = new Map();
for (let i = 0; i < nums.length; i++) {
count.set(nums[i], (count.get(nums[i]) || 0) + 1);
}
const out = [];
const threshold = nums.length / 3;
count.forEach(function(c, v) { if (c > threshold) out.push(v); });
return out.sort(function(a, b) { return a - b; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets