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.
1def majorityElement(nums):
2 counts = {}
3 for num in nums:
4 if num in counts:
5 counts[num]
Python utilizes a dictionary for counting, and then iterates through the dictionary to retrieve the majority element by scanning through its counts.
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
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.
JavaScript implements Boyer-Moore with clarity using similar logic paths as the algorithm, adjusting candidate and count accordingly.