Given a non-empty integer array nums of size n in which one element appears more than n/2 times. The existence of such an element is guaranteed. Return the majority element of the array.
Example 1
Input: nums = [2, 1, 1]
Output: 1
Explanation: The array contains 3 elements. The value 1 appears 2 times, which is more than 3 / 2.
Example 2
Input: nums = [-1, -1, -1, -1]
Output: -1
Explanation: The value -1 appears in all 4 positions, so it is the majority element.
Brute Force Approach
Brute-force counting treats each array value as a possible majority element. Scan the complete array and count how often that candidate occurs. A candidate whose frequency exceeds half of the array length is returned.
The same value may be counted several times when duplicates are encountered as candidates. This repeated scanning makes the method expensive, but it directly checks the definition of a majority element.
Algorithm
Compute the majority threshold as half of the array length, rounded down.
Visit each array value and treat it as the current candidate.
Scan the entire array and count the values equal to that candidate.
Return the candidate when its count becomes greater than the threshold.
Continue until a majority is found; the guarantee ensures that the outer loop always finds one.
Dry Run
Majority Element
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the majority element. int majorityElement(vector<int>& nums) { int n = nums.size(); int threshold = n / 2; // Test every array value as a possible majority candidate. for (int candidate : nums) { int frequency = 0; // Count the candidate across the complete array. for (int value : nums) { // Equal values contribute to the candidate's frequency. if (value == candidate) { frequency++; } } // A strict majority appears more than half of the time. if (frequency > threshold) { return candidate; } } return -1; }};// Driver codeint main() { vector<int> nums = {2, 1, 1}; // instance for class Solution Solution sol; cout << sol.majorityElement(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n²) in the worst case because up to n candidates can each trigger a scan of n values.
Space Complexity: O(1) auxiliary space because only counters and the current candidate are stored.
Better Approach
Instead of recounting a candidate from the beginning, a single traversal can store the frequency of every value. Each occurrence updates the value's existing count in a hash map.
As soon as one frequency exceeds half of the array length, that value satisfies the majority condition and can be returned.
Algorithm
Compute the majority threshold as half of the array length, rounded down.
Create an empty hash map from array values to their frequencies.
Traverse the array once and increase the current value's stored frequency.
After each update, compare that frequency with the majority threshold.
Return the current value as soon as its frequency is greater than the threshold.
The loop processes at most
nvalues; for a one-element array, the first update immediately returns its only value.
Dry Run
Hash Map
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the majority element. int majorityElement(vector<int>& nums) { int threshold = nums.size() / 2; unordered_map<int, int> frequencies; // Record each value and test its updated frequency. for (int value : nums) { frequencies[value]++; // The first frequency above the threshold identifies the majority. if (frequencies[value] > threshold) { return value; } } return -1; }};// Driver codeint main() { vector<int> nums = {2, 1, 1}; // instance for class Solution Solution sol; cout << sol.majorityElement(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) expected time because the array is traversed once and each hash-map update and lookup takes expected O(1) time.
Space Complexity: O(k), where k is the number of distinct values stored in the hash map. In the worst case, this is O(n) auxiliary space.
Optimal Approach
The hash map avoids repeated counting but still stores a frequency for every distinct value. Boyer-Moore voting keeps only one candidate and a balance counter.
Matching values increase the balance, while different values decrease it. This can be viewed as canceling pairs of different elements. Since the majority appears more often than all other values combined, every possible cancellation still leaves the majority as the final candidate.
Algorithm
Start with no active candidate and a balance of
0.Traverse the array from left to right.
When the balance is
0, select the current value as the new candidate.Increase the balance when the current value matches the candidate; otherwise, decrease it.
Continue until every array value has been processed.
Return the final candidate; for a one-element array, that element is selected and remains the candidate.
Dry Run
Majority Element -Opitmal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the majority element. int majorityElement(vector<int>& nums) { int candidate = 0; int balance = 0; // Cancel different values while preserving the strict majority. for (int value : nums) { // A zero balance starts a new candidate group. if (balance == 0) { candidate = value; } // Matching values add support; different values cancel support. if (value == candidate) { balance++; } else { balance--; } } return candidate; }};// Driver codeint main() { vector<int> nums = {2, 3, 2, 3, 3, 1, 3, 3}; // instance for class Solution Solution sol; cout << sol.majorityElement(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) because each array value is processed exactly once.
Space Complexity: O(1) auxiliary space because only the candidate and balance are stored.
Interview follow-up Questions
Every occurrence of a different value can cancel one occurrence of the majority value. The majority occurs more than all non-majority values combined, so it cannot be canceled completely. The candidate that survives after all pair cancellations must therefore be the guaranteed majority.
Be the first to add a comment.