Majority Element II
Description
Given an integer array of size n, find all elements that appear more than ⌊n/3⌋ times in the array.
Return a list of all such majority elements. The result can be returned in any order.
A key mathematical observation is that there can be at most two elements in any array that appear more than ⌊n/3⌋ times. This is because if three or more elements each appeared more than n/3 times, their combined count would exceed n, which is impossible since the array only has n elements.
Examples
Example 1
Input: nums = [3, 2, 3]
Output: [3]
Explanation: The array has 3 elements, so ⌊3/3⌋ = 1. We need elements appearing more than 1 time. The element 3 appears twice (at indices 0 and 2), while 2 appears only once. Since 2 > 1, element 3 qualifies as a majority element.
Example 2
Input: nums = [1]
Output: [1]
Explanation: The array has 1 element, so ⌊1/3⌋ = 0. We need elements appearing more than 0 times. The element 1 appears once, which is greater than 0, so it is a majority element.
Example 3
Input: nums = [1, 2]
Output: [1, 2]
Explanation: The array has 2 elements, so ⌊2/3⌋ = 0. Both elements appear once, which is greater than 0, so both qualify as majority elements.
Constraints
- 1 ≤ nums.length ≤ 5 × 10^4
- -10^9 ≤ nums[i] ≤ 10^9
Editorial
Brute Force
Intuition
The most straightforward way to solve this problem is to count how many times each element appears in the array and check whether that count exceeds the threshold ⌊n/3⌋.
Imagine you are a teacher collecting votes from a class. You pick each unique student name from a hat, then manually count how many times that name appears on all the ballots. If any name appears on more than a third of the ballots, you write it down as a winner.
For every element in the array, we scan the entire array to count its occurrences. If the count is greater than ⌊n/3⌋ and we have not already added it to our result, we include it.
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 3], threshold = ⌊3/3⌋ = 1:
Step 1: Start with i = 0, element nums[0] = 3. We need to count how many times 3 appears in the entire array.
Step 2: Scan the array to count occurrences of 3:
- nums[0] = 3 → match, count = 1
- nums[1] = 2 → no match, count = 1
- nums[2] = 3 → match, count = 2
- Final count of 3 = 2
Step 3: Is count(3) = 2 > threshold 1? YES. Add 3 to result. Result = [3].
Step 4: Move to i = 1, element nums[1] = 2. Count occurrences of 2:
- nums[0] = 3 → no match, count = 0
- nums[1] = 2 → match, count = 1
- nums[2] = 3 → no match, count = 1
- Final count of 2 = 1
Step 5: Is count(2) = 1 > threshold 1? NO (1 is not greater than 1). Do not add 2.
Step 6: Move to i = 2, element nums[2] = 3. We already processed 3, so skip.
Result: [3]
Brute Force — Counting Each Element's Frequency — For each element, we scan the entire array to count its occurrences and compare against the threshold ⌊n/3⌋.
Algorithm
- Calculate the threshold:
threshold = ⌊n/3⌋ - Initialize an empty result list
- For each element
nums[i]in the array:
a. Ifnums[i]is already in the result, skip it
b. Count the occurrences ofnums[i]by scanning the entire array
c. If the count is greater thanthreshold, addnums[i]to the result - Return the result list
Code
#include <vector>
using namespace std;
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
int threshold = n / 3;
vector<int> result;
for (int i = 0; i < n; i++) {
// Check if nums[i] is already in result
bool alreadyAdded = false;
for (int r : result) {
if (r == nums[i]) {
alreadyAdded = true;
break;
}
}
if (alreadyAdded) continue;
// Count occurrences of nums[i]
int count = 0;
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
if (count > threshold) {
result.push_back(nums[i]);
}
}
return result;
}
};class Solution:
def majorityElement(self, nums: list[int]) -> list[int]:
n = len(nums)
threshold = n // 3
result = []
for i in range(n):
# Skip if already in result
if nums[i] in result:
continue
# Count occurrences of nums[i]
count = 0
for j in range(n):
if nums[j] == nums[i]:
count += 1
if count > threshold:
result.append(nums[i])
return resultimport java.util.*;
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
int threshold = n / 3;
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
// Skip if already in result
if (result.contains(nums[i])) continue;
// Count occurrences of nums[i]
int count = 0;
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
if (count > threshold) {
result.add(nums[i]);
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(n²)
For each of the n elements, we perform a full scan of the array to count its occurrences, which takes O(n) time. In the worst case (all distinct elements), we do this for every element, giving n × n = O(n²) total operations.
Space Complexity: O(1)
The result list contains at most 2 elements (since at most 2 elements can appear more than ⌊n/3⌋ times). We use only a constant amount of extra variables. The output list does not count toward space complexity.
Why This Approach Is Not Efficient
The brute force approach has O(n²) time complexity. With n up to 5 × 10^4, that means up to 2.5 × 10^9 operations — far too slow for typical time limits of 1-2 seconds.
The core inefficiency is that we recount elements repeatedly. If the array is [1, 1, 1, 2, 2, 2, 3, 3, 3], we count the frequency of 1 three separate times (once for each occurrence of 1), doing redundant work.
What if we could count the frequency of every element in a single pass? A hash map lets us do exactly that — store each element's count as we encounter it, then filter for elements exceeding the threshold.
Better Approach - Hash Map Counting
Intuition
Instead of recounting each element from scratch, we can tally every element's frequency in a single pass through the array using a hash map. Think of it like sorting ballots into labeled piles: as each ballot comes in, you place it on the correct pile. At the end, you simply check which piles are tall enough (more than n/3 ballots).
We iterate through the array once, incrementing a counter in the hash map for each element. Then we iterate through the hash map entries and collect any element whose count exceeds ⌊n/3⌋.
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 3], threshold = ⌊3/3⌋ = 1:
Step 1: Initialize an empty hash map: freq = {}.
Step 2: Process nums[0] = 3.
- 3 is not in the map. Add it: freq = {3: 1}.
Step 3: Process nums[1] = 2.
- 2 is not in the map. Add it: freq = {3: 1, 2: 1}.
Step 4: Process nums[2] = 3.
- 3 is already in the map. Increment: freq = {3: 2, 2: 1}.
Step 5: Frequency counting complete. Now scan the map for entries with count > 1.
Step 6: Check entry (3, 2): Is 2 > 1? YES. Add 3 to result.
Step 7: Check entry (2, 1): Is 1 > 1? NO. Skip.
Result: [3]
Hash Map Frequency Counting — Build a frequency map in one pass, then filter for elements appearing more than ⌊n/3⌋ times.
Algorithm
- Calculate the threshold:
threshold = ⌊n/3⌋ - Create an empty hash map
freqto store element → count - For each element
numin the array:- If
numexists infreq, increment its count - Otherwise, set
freq[num] = 1
- If
- Initialize an empty result list
- For each
(key, count)pair infreq:- If
count > threshold, addkeyto result
- If
- Return the result list
Code
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
int threshold = n / 3;
unordered_map<int, int> freq;
// Count frequency of each element
for (int num : nums) {
freq[num]++;
}
// Collect elements exceeding threshold
vector<int> result;
for (auto& [val, count] : freq) {
if (count > threshold) {
result.push_back(val);
}
}
return result;
}
};class Solution:
def majorityElement(self, nums: list[int]) -> list[int]:
n = len(nums)
threshold = n // 3
freq = {}
# Count frequency of each element
for num in nums:
freq[num] = freq.get(num, 0) + 1
# Collect elements exceeding threshold
result = []
for val, count in freq.items():
if count > threshold:
result.append(val)
return resultimport java.util.*;
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
int threshold = n / 3;
Map<Integer, Integer> freq = new HashMap<>();
// Count frequency of each element
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// Collect elements exceeding threshold
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
if (entry.getValue() > threshold) {
result.add(entry.getKey());
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(n)
We make a single pass through the array of n elements to build the frequency map — each insertion/update in the hash map takes O(1) on average. Then we iterate through the map entries (at most n unique entries) to filter. Total: O(n) + O(n) = O(n).
Space Complexity: O(n)
In the worst case (all distinct elements), the hash map stores n key-value pairs. This additional space grows linearly with the input size.
Why This Approach Is Not Efficient
The hash map approach runs in O(n) time, which is already optimal in terms of time complexity. However, it uses O(n) extra space for the frequency map.
The problem's follow-up challenge asks: Can you solve it in O(n) time and O(1) space?
With up to 5 × 10^4 elements, the hash map could store tens of thousands of entries. While this is acceptable in practice, we can do better by leveraging a key mathematical insight: at most two elements can appear more than ⌊n/3⌋ times. This means we only need to track two candidates, not the frequency of every element.
The Boyer-Moore Voting Algorithm, extended for the n/3 threshold, achieves exactly this — O(n) time with O(1) space.
Optimal Approach - Boyer-Moore Voting Algorithm
Intuition
The Boyer-Moore Voting Algorithm is based on a clever "cancellation" strategy. The key insight is that at most two elements can appear more than ⌊n/3⌋ times in an array. So we only need to maintain two candidates with their running vote counts.
Think of it as a survival game with three-way battles. Imagine a crowd of people holding signs with numbers. Whenever three people hold three different numbers, all three leave the crowd simultaneously. After all such eliminations, whoever remains must be the strongest contenders — elements that appeared so frequently that even after losing votes to cancellations, they survived.
The algorithm works in two passes:
Pass 1 — Find candidates: We maintain two candidate slots, each with a value and a vote counter. As we process each element:
- If it matches a candidate, that candidate gains a vote
- If a candidate slot is empty (count is zero), the element claims that slot
- If neither condition applies, both candidates lose a vote (the three-way cancellation)
Pass 2 — Verify candidates: The first pass gives us at most two potential majority elements, but they might be false positives. We count their actual occurrences to confirm they truly exceed the ⌊n/3⌋ threshold.
The reason verification is needed: the cancellation process guarantees that any true majority element will survive as a candidate, but non-majority elements can also survive if they happen to be the last ones standing after all cancellations.
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 3, 1, 3, 2, 1, 1], n = 8, threshold = ⌊8/3⌋ = 2:
Pass 1 — Finding Candidates:
Step 1: Initialize candidates: cand1 = None (count1 = 0), cand2 = None (count2 = 0).
Step 2: Process nums[0] = 3. count1 is 0 → claim slot 1. Set cand1 = 3, count1 = 1.
Step 3: Process nums[1] = 2. Does not match cand1 (3). count2 is 0 → claim slot 2. Set cand2 = 2, count2 = 1.
Step 4: Process nums[2] = 3. Matches cand1 (3) → increment count1 to 2.
Step 5: Process nums[3] = 1. Does not match cand1 (3) or cand2 (2). Both counts > 0 → cancel: count1 = 1, count2 = 0.
Step 6: Process nums[4] = 3. Matches cand1 (3) → increment count1 to 2.
Step 7: Process nums[5] = 2. Does not match cand1 (3). count2 is 0 → claim slot 2. Set cand2 = 2, count2 = 1.
Step 8: Process nums[6] = 1. Does not match cand1 (3) or cand2 (2). Both counts > 0 → cancel: count1 = 1, count2 = 0.
Step 9: Process nums[7] = 1. Does not match cand1 (3). count2 is 0 → claim slot 2. Set cand2 = 1, count2 = 1.
After Pass 1: cand1 = 3 (count1 = 1), cand2 = 1 (count2 = 1).
Pass 2 — Verification:
Step 10: Count actual occurrences of candidate 3: appears at indices 0, 2, 4 → count = 3. Is 3 > 2? YES.
Step 11: Count actual occurrences of candidate 1: appears at indices 3, 6, 7 → count = 3. Is 3 > 2? YES.
Result: [3, 1]
Boyer-Moore Voting — Two-Candidate Survival Game — Watch how two candidate slots compete and survive through vote increments and three-way cancellations, followed by a verification pass.
Algorithm
Pass 1 — Candidate Selection:
- Initialize two candidate variables
cand1,cand2with distinct values and two counterscount1 = 0,count2 = 0 - For each element
numin the array:- If
num == cand1, incrementcount1 - Else if
num == cand2, incrementcount2 - Else if
count1 == 0, setcand1 = num,count1 = 1 - Else if
count2 == 0, setcand2 = num,count2 = 1 - Else, decrement both
count1andcount2
- If
Pass 2 — Verification:
3. Count actual occurrences of cand1 and cand2 in the array
4. Add each candidate to the result if its count exceeds ⌊n/3⌋
5. Return the result
Code
#include <vector>
using namespace std;
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
// Pass 1: Find candidates using Boyer-Moore Voting
int cand1 = 0, cand2 = 1; // Initialize to different values
int count1 = 0, count2 = 0;
for (int num : nums) {
if (num == cand1) {
count1++;
} else if (num == cand2) {
count2++;
} else if (count1 == 0) {
cand1 = num;
count1 = 1;
} else if (count2 == 0) {
cand2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
// Pass 2: Verify candidates
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == cand1) count1++;
else if (num == cand2) count2++;
}
int threshold = n / 3;
vector<int> result;
if (count1 > threshold) result.push_back(cand1);
if (count2 > threshold) result.push_back(cand2);
return result;
}
};class Solution:
def majorityElement(self, nums: list[int]) -> list[int]:
n = len(nums)
# Pass 1: Find candidates using Boyer-Moore Voting
cand1, cand2 = 0, 1 # Initialize to different values
count1, count2 = 0, 0
for num in nums:
if num == cand1:
count1 += 1
elif num == cand2:
count2 += 1
elif count1 == 0:
cand1 = num
count1 = 1
elif count2 == 0:
cand2 = num
count2 = 1
else:
count1 -= 1
count2 -= 1
# Pass 2: Verify candidates
count1 = 0
count2 = 0
for num in nums:
if num == cand1:
count1 += 1
elif num == cand2:
count2 += 1
threshold = n // 3
result = []
if count1 > threshold:
result.append(cand1)
if count2 > threshold:
result.append(cand2)
return resultimport java.util.*;
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
// Pass 1: Find candidates using Boyer-Moore Voting
int cand1 = 0, cand2 = 1; // Initialize to different values
int count1 = 0, count2 = 0;
for (int num : nums) {
if (num == cand1) {
count1++;
} else if (num == cand2) {
count2++;
} else if (count1 == 0) {
cand1 = num;
count1 = 1;
} else if (count2 == 0) {
cand2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
// Pass 2: Verify candidates
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == cand1) count1++;
else if (num == cand2) count2++;
}
int threshold = n / 3;
List<Integer> result = new ArrayList<>();
if (count1 > threshold) result.add(cand1);
if (count2 > threshold) result.add(cand2);
return result;
}
}Complexity Analysis
Time Complexity: O(n)
We make two linear passes through the array. The first pass identifies candidates in O(n) time — each element involves only constant-time comparisons and counter updates. The second pass counts occurrences of at most two candidates, also O(n). Total: O(n) + O(n) = O(n).
Space Complexity: O(1)
We use only a fixed number of variables: two candidate values, two counters, and a threshold. The result list contains at most 2 elements. No auxiliary data structures that grow with input size are used. This is a significant improvement over the hash map approach which required O(n) space.