Given an integer array nums of length n. Return every element that appears more than n/3 times in the array.
Example 1
Input: nums = [1, 2, 3, 1, 2, 1, 2, 4, 2, 1]
Output: [1, 2]
Explanation: The array contains 10 elements, so a valid answer must appear more than ⌊10/3⌋ = 3 times. Both 1 and 2 appear 4 times. No other value crosses the threshold.
Example 2
Input: nums = [-1, -1, -1, 2, 3, 2, 2]
Output: [-1, 2]
Explanation: The array contains 7 elements, so the required frequency is greater than ⌊7/3⌋ = 2. The values -1 and 2 each appear 3 times.
Brute Force Approach
Treat every array value as a possible answer. Count how many times each candidate appears across the complete array and add it when its frequency is greater than ⌊n/3⌋.
The same candidate may appear at several indices, so it must not be added more than once.
Algorithm
Compute the threshold by dividing the array length by
3, and create an empty result list that can hold at most two distinct answers.Move an outer index from the first position to the last, treating the value at that position as the current candidate.
Move an inner index across the full array and count every value equal to the current candidate.
Add the candidate when its count exceeds the threshold and it is not already in the result.
Stop early after two answers are found; otherwise, finish when the outer index reaches the end. A one-element array counts and returns its only value.
Dry Run
Majority element II brute force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns all elements appearing more than one-third of the time. vector<int> majorityElement(vector<int>& nums) { int n = nums.size(); int threshold = n / 3; vector<int> answer; // Test the value at every index as a possible qualifying candidate. for (int candidateIndex = 0; candidateIndex < n; candidateIndex++) { int candidate = nums[candidateIndex]; int frequency = 0; // Count the current candidate with an index-controlled full scan. for (int scanIndex = 0; scanIndex < n; scanIndex++) { // Equal values contribute to the candidate's frequency. if (nums[scanIndex] == candidate) { frequency++; } } bool notAdded = find(answer.begin(), answer.end(), candidate) == answer.end(); // Store a qualifying candidate only once. if (frequency > threshold && notAdded) { answer.push_back(candidate); } // No third value can occur more than one-third of the time. if (answer.size() == 2) { break; } } return answer; }};// Driver codeint main() { vector<int> nums = {1, 2, 3, 1, 2, 1, 2, 4, 2, 1}; // instance for class Solution Solution sol; vector<int> answer = sol.majorityElement(nums); int answerSize = answer.size(); // Print every qualifying value returned by the solution. for (int index = 0; index < answerSize; index++) { cout << answer[index] << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n²) in the worst case because as many as n candidates can each trigger a complete scan of n values. Checking the result list takes constant time because it contains at most two elements.
Space Complexity: O(1) auxiliary space because the result contains at most two values and only counters are otherwise stored. The returned list is commonly excluded from auxiliary-space analysis.
Better Approach
Instead of recounting every candidate from the beginning, a hash map can store the final frequency of each distinct value. Once the counts are complete, the map already contains all the information needed to identify values whose frequency is greater than ⌊n/3⌋.
Algorithm
Compute the threshold as the array length divided by
3, and create an empty hash map and result list.Traverse the array once and increase the stored frequency of each value.
Traverse the array again, read each value's final frequency, and add it when the frequency exceeds the threshold and the value is not already in the result.
Stop after two values are added or when the second traversal ends.
For a one-element array, its frequency becomes
1, which is greater than the threshold0.
Dry Run
Majority Element II
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns all elements appearing more than one-third of the time. vector<int> majorityElement(vector<int>& nums) { int threshold = nums.size() / 3; map<int, int> frequency; vector<int> answer; // Store the final frequency of every distinct value. for (int value : nums) { frequency[value]++; } // Inspect each distinct value directly in ascending key order. for (const auto& entry : frequency) { // Store the value when its final frequency crosses the threshold. if (entry.second > threshold) { answer.push_back(entry.first); } // At most two distinct values can satisfy the condition. if (answer.size() == 2) { break; } } return answer; }};// Driver codeint main() { vector<int> nums = {1, 2, 3, 1, 2, 1, 2, 4, 2, 1}; // instance for class Solution Solution sol; vector<int> answer = sol.majorityElement(nums); // Print every qualifying value returned by the solution. for (int value : answer) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n) because building and ordering the frequency map requires logarithmic work.
Space Complexity: O(n) in the worst case because the map may store every distinct array value.
Optimal Approach
The ordered map stores frequencies for all distinct values, even though the result can contain at most two elements. If three values each exceeded the one-third threshold, their combined frequency would be greater than n. The extended Boyer–Moore Voting Algorithm therefore keeps only two candidates and two counters.
When a value matches a candidate, that candidate's counter increases. An empty candidate slot accepts a new value. If the current value matches neither candidate and both slots are active, one occurrence is cancelled from each candidate counter. This cancellation removes a group of three different values, which cannot change which values may occur more than ⌊n/3⌋ times.
The first traversal produces only possible candidates. A second traversal must verify their real frequencies because the problem does not guarantee that any qualifying value exists.
Algorithm
Initialize two candidate slots with counters set to zero because the result can contain at most two qualifying values.
Traverse the array, increase a counter when its candidate matches, and assign the current value to an empty slot when no active candidate matches.
Otherwise, cancel one vote from both candidates because three different values have been encountered.
After the first traversal ends, reset two verification counts and scan the array again to count the real occurrences of the distinct candidates.
Add each candidate whose verified frequency exceeds
⌊n/3⌋; a one-element array verifies its only candidate successfully.
Dry Run
Optimal approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns all elements appearing more than one-third of the time. vector<int> majorityElement(vector<int>& nums) { int candidate1 = nums[0]; int candidate2 = nums[0]; int count1 = 0; int count2 = 0; // Select at most two possible candidates through vote cancellation. for (int value : nums) { // A match strengthens the first candidate. if (value == candidate1) { count1++; } // A match strengthens the second candidate. else if (value == candidate2) { count2++; } // An empty first slot accepts the current value as its candidate. else if (count1 == 0) { candidate1 = value; count1 = 1; } // An empty second slot accepts the current value as its candidate. else if (count2 == 0) { candidate2 = value; count2 = 1; } // A third distinct value cancels one vote from both candidates. else { count1--; count2--; } } int verified1 = 0; int verified2 = 0; // Count the real frequencies of the selected candidates. for (int value : nums) { // An occurrence of the first candidate increases its verified count. if (value == candidate1) { verified1++; } // An occurrence of the second candidate increases its verified count. else if (value == candidate2) { verified2++; } } int threshold = nums.size() / 3; vector<int> answer; // Include the first candidate only when its real frequency qualifies. if (verified1 > threshold) { answer.push_back(candidate1); } // Include a distinct second candidate only when it also qualifies. if (candidate2 != candidate1 && verified2 > threshold) { answer.push_back(candidate2); } return answer; }};// Driver codeint main() { vector<int> nums = {1, 2, 3, 1, 2, 1, 2, 4, 2, 1}; // instance for class Solution Solution sol; vector<int> answer = sol.majorityElement(nums); // Print every qualifying value returned by the solution. for (int value : answer) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) because one traversal selects the candidates and a second traversal verifies their actual frequencies.
Space Complexity: O(1) auxiliary space because only two candidates, four counters, and a result of at most two values are stored. The returned list is commonly excluded from auxiliary-space analysis.
Interview follow-up Questions
Every answer must appear at least ⌊n/3⌋ + 1 times. If three distinct values each appeared that often, their combined frequency would be greater than n, which is impossible. Therefore, only two candidate slots are needed.
Be the first to add a comment.