Majority Element II solution and explanation
Google
TCS
9 more videos on this problem
Majority Element II - Leetcode 229 - PythonNeetCodeIO · 14:34 · 45K views
Majority Element II | Leet code 229 | Theory explained + Python codeSai Anish Malla · 18:39 · 3K views
19. Leetcode 229. Majority Element II : JAVAWeb Fusion with Bharadwaj · 11:21 · 358 views
LeetCode 229: ✅ Easy and Advanced Approaches to Solve Majority Element II 🚀The algorithm Architect · 8:16 · 261 views
Majority Element II | LeetCode 229 | September LeetCode Challenge | Day 22Learn Code Repeat · 12:37 · 237 views
LeetCode 229 Majority Element II - HashMap SolutionAlgorithmicIQ · 2:50 · 144 views
Majority Element II - Leetcode 229 | Extended Boyer–Moore in JavaScriptWeb Coder Abhishek · 10:25 · 141 views
Majority Element II | 229 Leetcode | Python3CodeMeThere · 4:56 · 69 views
229: Majority Element II | LeetCode's | C++ Tutorial | Code ExplainedLearning Decoded · 3:42 · 67 views
Majority Element II | Leetcode 229Next Door Professor · 22:21 · 63 views
The problem
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3] Output: [3]
Example 2:
Input: nums = [1] Output: [1]
Example 3:
Input: nums = [1,2] Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
Approach overview
Problem Overview: Given an integer array nums, return all elements that appear more than ⌊n/3⌋ times. Unlike the classic majority element problem (n/2), this variant can have at most two valid answers because three distinct numbers appearing more than n/3 times would exceed the array length.
Approach 1: HashMap Counting Technique (O(n) time, O(n) space)
This method directly counts the frequency of every element using a hash map. Iterate through the array and increment the count for each number with a constant-time hash lookup. After building the frequency table, iterate over the map and collect keys whose counts exceed ⌊n/3⌋. The approach is straightforward and works for any distribution of numbers because it explicitly tracks counts.
This solution relies on a hash table for fast insert and lookup operations. It runs in O(n) time since each element is processed once, but it requires O(n) extra space to store frequencies. You would typically use this approach when clarity and quick implementation matter more than memory optimization.
Approach 2: Boyer-Moore Voting Algorithm Extension (O(n) time, O(1) space)
The optimal solution extends the Boyer-Moore majority vote algorithm. Because at most two elements can appear more than n/3 times, maintain two candidate values and their counters. Iterate through the array and update counters using a cancellation principle: matching numbers increment the corresponding counter, empty counters adopt a new candidate, and mismatches decrement both counters.
After the first pass, the candidates are potential majority elements but not guaranteed. Run a second pass through the array to verify their actual counts and include only those exceeding ⌊n/3⌋. This algorithm works because non-majority elements cancel each other out during the voting process. The result is O(n) time with only O(1) additional memory, making it extremely efficient for large inputs.
Recommended for interviews: Interviewers usually expect the Boyer-Moore extension. The hash map approach shows you understand frequency counting with a counting strategy, but the optimal solution demonstrates deeper algorithmic reasoning and space optimization. Start with the counting idea if needed, then refine it to the constant-space voting technique.
Approach 1: HashMap Counting Technique
This approach leverages a hashmap to count the occurrences of each element in the input array. We iterate through the array once to populate the hashmap and then make another pass to find all elements whose count is greater than ⌊n/3⌋. While this method is straightforward and simple to implement, it uses extra space proportional to the number of unique elements.
from typing import List
from collections import defaultdict
def majorityElement(nums: List[int]) -> List[int]:
countMap = defaultdict(int)
limit = len(nums) // 3
for num in nums:
countMap[num] += 1
return [num for num, count in countMap.items() if count > limit]
# Example Usage
nums = [3, 2, 3]
print(majorityElement(nums))import java.util.*;
public class MajorityElement {
public List<Integer> majorityElement(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
int limit = nums.length / 3;
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
if (entry.getValue() > limit) {
result.add(entry.getKey());
}
}
return result;
}
public static void main(String[] args) {
MajorityElement me = new MajorityElement();
int[] nums = {3, 2, 3};
List<Integer> result = me.majorityElement(nums);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> countMap;
int limit = nums.size() / 3;
for (int num : nums) {
countMap[num]++;
}
vector<int> result;
for (auto& entry : countMap) {
if (entry.second > limit) {
result.push_back(entry.first);
}
}
return result;
}
int main() {
vector<int> nums = {3, 2, 3};
vector<int> result = majorityElement(nums);
for (int num : result) {
cout << num << " ";
}
return 0;
}function majorityElement(nums) {
const countMap = {};
const limit = Math.floor(nums.length / 3);
for (const num of nums) {
countMap[num] = (countMap[num] || 0) + 1;
}
return Object.keys(countMap).filter(num => countMap[num] > limit).map(Number);
}
// Example usage
const nums = [3, 2, 3];
console.log(majorityElement(nums));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Define a simple hash map structure
typedef struct {
int key;
int count;
} Element;
Element* createMap(int size) {
Element *elements = (Element*) malloc(size * sizeof(Element));
for (int i = 0; i < size; i++) {
elements[i].key = INT_MIN;
elements[i].count = 0;
}
return elements;
}
void addItem(Element* map, int size, int num) {
for (int i = 0; i < size; i++) {
if (map[i].key == num || map[i].key == INT_MIN) {
if (map[i].key == INT_MIN) map[i].key = num;
map[i].count++;
return;
}
}
}
int* majorityElement(int* nums, int numsSize, int* returnSize) {
int limit = numsSize / 3;
Element* countMap = createMap(numsSize);
for (int i = 0; i < numsSize; i++) {
addItem(countMap, numsSize, nums[i]);
}
int *result = (int*) malloc(numsSize * sizeof(int));
*returnSize = 0;
for (int i = 0; i < numsSize; i++) {
if (countMap[i].key != INT_MIN && countMap[i].count > limit) {
result[*returnSize] = countMap[i].key;
(*returnSize)++;
}
}
free(countMap);
return result;
}
int main() {
int nums[] = {3,2,3};
int returnSize;
int* result = majorityElement(nums, 3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> MajorityElement(int[] nums) {
Dictionary<int, int> countMap = new Dictionary<int, int>();
int limit = nums.Length / 3;
foreach (int num in nums) {
if (!countMap.ContainsKey(num)) {
countMap[num] = 0;
}
countMap[num]++;
}
IList<int> result = new List<int>();
foreach (var entry in countMap) {
if (entry.Value > limit) {
result.Add(entry.Key);
}
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 3};
IList<int> result = sol.MajorityElement(nums);
foreach (int num in result) {
Console.Write(num + " ");
}
}
}This Python solution uses a defaultdict from the collections module to track counts of each element in the array. We make one pass to fill the dictionary with counts and another to determine which elements exceed the ⌊n/3⌋ criterion. Using defaultdict simplifies the counting logic by providing default values.
Time Complexity: O(n), where n is the number of elements in the list.
Space Complexity: O(m), where m is the number of distinct elements in the list.
Approach 2: Boyer-Moore Voting Algorithm Extension
The Boyer-Moore Voting Algorithm is optimized for finding the majority element which appears more than n/2 times. Here, we extend it to handle the case for n/3 by maintaining up to two potential candidates, since at most two elements can qualify for appearing more than ⌊n/3⌋ times. In the first pass, we identify the element candidates by attempting to cancel them out against others. A second pass is required to confirm the counts of these candidates to ensure they appear more than ⌊n/3⌋ times.
from typing import List
def majorityElement(nums: List[int]) -> List[int]:
candidate1, candidate2, count1, count2 = 0, 0, 0, 0
for num in nums:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = num, 1
elif count2 == 0:
candidate2, count2 = num, 1
else:
count1, count2 = count1 - 1, count2 - 1
count1, count2 = 0, 0
for num in nums:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
result = []
n = len(nums)
if count1 > n // 3:
result.append(candidate1)
if count2 > n // 3:
result.append(candidate2)
return result
# Example Usage
nums = [3, 2, 3]
print(majorityElement(nums))import java.util.*;
public class Solution {
public List<Integer> majorityElement(int[] nums) {
int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
}
List<Integer> result = new ArrayList<>();
if (count1 > nums.length / 3) result.add(candidate1);
if (count2 > nums.length / 3) result.add(candidate2);
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 3};
List<Integer> result = sol.majorityElement(nums);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
}
vector<int> result;
if (count1 > nums.size() / 3) result.push_back(candidate1);
if (count2 > nums.size() / 3) result.push_back(candidate2);
return result;
}
};
int main() {
Solution sol;
vector<int> nums = {3, 2, 3};
vector<int> result = sol.majorityElement(nums);
for (int num : result) {
cout << num << " ";
}
return 0;
}function majorityElement(nums) {
let candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
for (const num of nums) {
if (num === candidate1) {
count1++;
} else if (num === candidate2) {
count2++;
} else if (count1 === 0) {
candidate1 = num;
count1 = 1;
} else if (count2 === 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (const num of nums) {
if (num === candidate1) {
count1++;
} else if (num === candidate2) {
count2++;
}
}
const result = [];
const limit = Math.floor(nums.length / 3);
if (count1 > limit) {
result.push(candidate1);
}
if (count2 > limit) {
result.push(candidate2);
}
return result;
}
// Example usage
const nums = [3, 2, 3];
console.log(majorityElement(nums));#include <stdio.h>
#include <stdlib.h>
int* majorityElement(int* nums, int numsSize, int* returnSize) {
int candidate1 = 0, candidate2 = 0;
int count1 = 0, count2 = 0;
*returnSize = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == candidate1) {
count1++;
}
else if (nums[i] == candidate2) {
count2++;
}
else if (count1 == 0) {
candidate1 = nums[i];
count1 = 1;
}
else if (count2 == 0) {
candidate2 = nums[i];
count2 = 1;
}
else {
count1--;
count2--;
}
}
// Verify the candidates
count1 = count2 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == candidate1) count1++;
else if (nums[i] == candidate2) count2++;
}
int* result = (int*) malloc(2 * sizeof(int));
if (count1 > numsSize / 3) result[(*returnSize)++] = candidate1;
if (count2 > numsSize / 3) result[(*returnSize)++] = candidate2;
return result;
}
int main() {
int nums[] = {3, 2, 3};
int returnSize;
int* result = majorityElement(nums, 3, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> MajorityElement(int[] nums) {
int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
foreach (int num in nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
foreach (int num in nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
}
}
IList<int> result = new List<int>();
if (count1 > nums.Length / 3) {
result.Add(candidate1);
}
if (count2 > nums.Length / 3) {
result.Add(candidate2);
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 3};
IList<int> result = sol.MajorityElement(nums);
foreach (int num in result) {
Console.Write(num + " ");
}
}
}This Python solution forgoes additional data structures after identifying two potential majority elements, using Boyer-Moore to compute and verify candidates, then reconfirming the majority counts in a secondary pass.
Time Complexity: O(n), iterating over the array twice.
Space Complexity: O(1), no extra collections are used apart from fixed counters.
Approach 3: Default Approach
func majorityElement(nums []int) []int {
var n1, n2 int
m1, m2 := 0, 1
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
} else if n1 == 0 {
m1, n1 = m, 1
} else if n2 == 0 {
m2, n2 = m, 1
} else {
n1, n2 = n1-1, n2-1
}
}
n1, n2 = 0, 0
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
}
}
var ans []int
if n1 > len(nums)/3 {
ans = append(ans, m1)
}
if n2 > len(nums)/3 {
ans = append(ans, m2)
}
return ans
}class Solution {
/**
* @param Integer[] $nums
* @return Integer[]
*/
function majorityElement($nums) {
$rs = [];
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
$hashmap[$nums[$i]] += 1;
if ($hashmap[$nums[$i]] > $n / 3) {
array_push($rs, $nums[$i]);
}
}
return array_unique($rs);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap Counting Technique | Time Complexity: O(n), where n is the number of elements in the list. |
| Boyer-Moore Voting Algorithm Extension | Time Complexity: O(n), iterating over the array twice. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting Technique | O(n) | O(n) | Best for quick implementation or when extra memory is not a concern. |
| Boyer-Moore Voting Algorithm Extension | O(n) | O(1) | Preferred in interviews and memory-constrained environments. |
Frequently asked questions
Is Majority Element II easy or hard?
Majority Element II is considered a Medium difficulty problem. The counting approach with a hash map is straightforward, but deriving the Boyer-Moore extension that tracks two candidates requires deeper understanding of voting and element cancellation techniques.
How to solve Majority Element II in O(n)?
Use the Boyer-Moore Voting Algorithm extension. Maintain two candidate values and their counters while iterating through the array. Elements cancel each other out when they differ from the current candidates. After the first pass, verify the remaining candidates with a second pass to ensure their counts exceed ⌊n/3⌋.
Majority Element II Python or Java solution?
Python and Java implementations typically use either a HashMap for counting frequencies or the Boyer-Moore voting extension for constant-space optimization. The hash map solution is simpler to implement, while the Boyer-Moore approach achieves O(n) time and O(1) space, which is preferred for interviews.
What is the best approach for Majority Element II?
The Boyer-Moore Voting Algorithm extension is the most efficient approach. It finds up to two candidates that may appear more than n/3 times by using a cancellation technique while iterating through the array. After identifying candidates, a second pass verifies their counts. This solution runs in O(n) time with O(1) extra space.
What data structure is used in Majority Element II?
Common solutions use either a hash table or constant-space counters. The hash map approach stores element frequencies for quick lookup, while the Boyer-Moore algorithm tracks two candidate elements and their counts without extra storage. Both operate on a simple array traversal.
What is the time complexity of Majority Element II?
The optimal solution runs in O(n) time because the array is scanned at most twice—once to determine potential candidates and once to verify their frequencies. The space complexity is O(1) when using the Boyer-Moore voting approach. A hash map counting method also runs in O(n) time but requires O(n) space.
Is Majority Element II asked at Google, Amazon, or Meta?
Majority Element II appears in coding interview practice sets and has been reported in interview preparation resources for companies like Amazon and Meta. The problem tests understanding of array traversal, frequency counting, and the Boyer-Moore voting algorithm—concepts commonly evaluated in technical interviews.