Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3] Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109O(1) space?The goal of #169 Majority Element is to find the element that appears more than n/2 times in an array. Because the majority element is guaranteed to exist, we can design optimized approaches that avoid checking every possible candidate.
A straightforward strategy is to use a hash table to count the frequency of each element while iterating through the array. As soon as a count exceeds n/2, that value is the majority element. Another simple idea is sorting the array—since the majority element appears more than half the time, it must occupy the middle index after sorting.
The most optimal solution uses the Boyer–Moore Voting Algorithm. It keeps a candidate and a counter that increases when the same element appears and decreases otherwise. Because the majority element dominates the array, it survives the cancellation process and remains the final candidate.
Some interview discussions also mention a divide and conquer approach that recursively finds majority candidates in subarrays and combines them.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Counting | O(n) | O(n) |
| Sorting | O(n log n) | O(1) or O(log n) |
| Boyer–Moore Voting | O(n) | O(1) |
| Divide and Conquer | O(n log n) | O(log n) |
take U forward
This approach involves counting the frequency of each element using a HashMap (or a Dictionary). We store each element as a key and maintain its count as the value. Finally, we determine which key has a count greater than half the length of the array.
Time Complexity: O(n) as we traverse the array twice, Space Complexity: O(n) since we use an additional data structure to store counts.
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6int majorityElement(vector<int>& nums) {
7 unordered_map<int, int> countMap;
8 for (int num : nums) {
9 countMap[num]++;
10 }
11 int majorityCount = nums.size() / 2;
12 for (auto& [num, count] : countMap) {
13 if (count > majorityCount) {
14 return num;
}
}
return -1; // never hit due to problem assumptions
}
int main() {
vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
cout << majorityElement(nums);
return 0;
}In C++, we use an unordered_map to maintain the counts of each element. After counting, we iterate over this map to return the number with the highest frequency.
The Boyer-Moore Voting Algorithm is an efficient solution that processes the array in a single pass. It maintains a count for the majority candidate. At the end of the loop, since the majority element exists, the candidate will be the majority element.
Time Complexity: O(n) as it traverses the array once, Space Complexity: O(1) because no extra space is used except for variables.
1
class MajorityElementSolver {
public static int MajorityElement(int[] nums) {
int count = 0, candidate = 0;
foreach (int num in nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
static void Main() {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
Console.WriteLine(MajorityElement(nums));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Majority Element is a classic interview problem frequently asked at companies like Amazon, Google, and Meta. Interviewers use it to test understanding of array processing, counting strategies, and optimized algorithms like Boyer–Moore.
The optimal approach is the Boyer–Moore Voting Algorithm. It scans the array once while maintaining a candidate and counter, giving O(n) time and O(1) space complexity.
A hash map is a common and intuitive choice because it tracks frequencies of elements as you iterate. However, while easy to implement, it uses O(n) extra space compared to the constant-space Boyer–Moore method.
The algorithm works because the majority element appears more than half the time. By canceling out different elements through increment and decrement operations, the true majority element remains as the final candidate.
C# uses the Boyer-Moore algorithm to simplify the operation of ensuring majority element finding in a controlled pass through the array.