Author at SyntaxFlow
Given an integer array nums of size n, find all elements that appear more than ⌊n/3⌋ times.
Return the elements in any order.
1 <= nums.length <= 5 × 10⁴-10⁹ <= nums[i] <= 10⁹There can be at most two elements in the array that appear more than ⌊n/3⌋ times.
Input
nums = [3, 2, 3]
Output
[3]
Explanation
The array size is 3, so:
⌊3/3⌋ = 1
Element 3 appears 2 times, which is greater than 1.
Input
nums = [1]
Output
[1]
Explanation
The array size is 1, so:
⌊1/3⌋ = 0
Element 1 appears once, which is greater than 0.
Input
nums = [1, 2]
Output
[1, 2]
Explanation
The array size is 2, so:
⌊2/3⌋ = 0
Both elements appear more than 0 times.
The simplest way to solve this problem is to check the frequency of every element individually.
For each element in the array, traverse the entire array and count how many times it appears. If its frequency is greater than ⌊n/3⌋, add it to the result.
Since there can be at most two majority elements, we can stop once we find two valid elements.
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
vector<int> result;
for (int i = 0; i < n; i++) {
int count = 0;
// Count frequency of nums[i]
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) {
count++;
}
}
// Check if frequency is greater than n/3
if (count > n / 3) {
bool alreadyPresent = false;
// Avoid duplicates in result
for (int num : result) {
if (num == nums[i]) {
alreadyPresent = true;
break;
}
}
if (!alreadyPresent) {
result.push_back(nums[i]);
}
}
// At most two majority elements can exist
if (result.size() == 2) {
break;
}
}
sort(result.begin(), result.end());
return result;
}
};Time Complexity
Time Complexity: O(n²)
Space Complexity
Space Complexity: O(1)
An element must appear more than ⌊n/3⌋ times.
If there were 3 such elements, then the total count would exceed n:
(n/3 + 1) + (n/3 + 1) + (n/3 + 1) > nwhich is impossible.
Therefore, there can be at most two majority elements.
For an element to be considered a majority element in this problem, its frequency must be greater than ⌊n/3⌋.
There can be at most two majority elements in the array. This is because if three different elements each appeared more than ⌊n/3⌋ times, their total frequency would exceed n, which is impossible.
Therefore, instead of tracking all elements, we only need to track:
The Boyer-Moore Voting Algorithm is based on the idea of cancellation.
Consider the array:
[2, 2, 2, 1, 1, 1, 3]
The majority elements are 2 and 1.
If we remove one occurrence each of:
The remaining array becomes:
[2, 2, 1, 1]
The majority elements remain unchanged.
This means that whenever we encounter a third distinct element, we can safely reduce the counts of both current candidates. This process gradually eliminates non-majority elements while preserving potential majority candidates.
For every element in the array:
Case 1: Element matches Candidate 1
Increase Count 1.
Case 2: Element matches Candidate 2
Increase Count 2.
Case 3: Count 1 is 0
Assign the current element as Candidate 1 and set Count 1 to 1.
Case 4: Count 2 is 0
Assign the current element as Candidate 2 and set Count 2 to 1.
Case 5: Element matches neither candidate
Decrease both Count 1 and Count 2.
This is known as the cancellation step.
The first traversal of the array is used to identify two potential majority elements.
At the end of this pass:
These candidates are not guaranteed to be majority elements.
Consider the array:
[1, 2, 3, 4]
The algorithm may still end up with two candidates after the first pass. However, none of them actually appear more than ⌊n/3⌋ times.
Therefore, we must verify the frequencies of the selected candidates.
Traverse the array again and count the actual frequencies of Candidate 1 and Candidate 2.
If a candidate appears more than ⌊n/3⌋ times, add it to the answer.
Otherwise, ignore it.
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int candidate1 = -1, candidate2 = -1;
int count1 = 0, count2 = 0;
// First Pass: Find potential candidates
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--;
}
}
// Second Pass: Verify candidates
count1 = 0;
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;
}
};Time Complexity
O(n)
Space Complexity
O(1)
Only two candidates and two counters are maintained throughout the algorithm.
problem link:
Majority Element II - LeetCode
Video references: