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] <= 109Follow-up: Could you solve the problem in linear time and in
O(1) space?Problem Overview: You are given an integer array nums. One element appears more than n/2 times, where n is the array length. Return that element. The majority element is guaranteed to exist, so the task becomes identifying it efficiently.
Approach 1: HashMap Counting (Time: O(n), Space: O(n))
Count how many times each number appears while iterating through the array once. Use a hash table where the key is the number and the value is its frequency. Each step performs a constant-time hash lookup and increment. As soon as a count exceeds n/2, you can return the element immediately. This approach is straightforward and easy to implement, making it a good baseline when working with problems involving frequency counting in an array. The tradeoff is extra memory proportional to the number of unique values.
Approach 2: Sorting (Time: O(n log n), Space: O(1) or O(log n))
Sort the array and return the element at index n/2. Because the majority element appears more than half the time, it must occupy the middle position after sorting. This works because any element occurring more than half the array length dominates the central region of the sorted sequence. The implementation is extremely simple but sorting increases the runtime to O(n log n). Useful when sorting is already required elsewhere in the pipeline or when minimizing implementation complexity matters more than optimal time complexity.
Approach 3: Boyer-Moore Voting Algorithm (Time: O(n), Space: O(1))
This algorithm keeps a candidate and a count. Iterate through the array once. When the count becomes zero, set the current element as the new candidate. If the current element matches the candidate, increment the count; otherwise decrement it. The key insight: pairs of different elements cancel each other out, leaving the majority element as the final candidate. This elegant technique relies on the mathematical guarantee that a majority element exists. It avoids extra memory and performs only a single pass, making it the optimal solution for most interviews involving arrays and frequency dominance problems often discussed alongside hash tables or divide and conquer strategies.
Recommended for interviews: Interviewers typically expect the Boyer-Moore Voting Algorithm because it demonstrates deeper algorithmic thinking and achieves O(n) time with O(1) space. The HashMap solution still shows solid problem understanding and is often accepted as an initial approach before optimizing. Moving from counting with extra memory to Boyer-Moore highlights your ability to refine solutions under tighter constraints.
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.
In C, we use a large-sized array as a hash table since specific implementations of dynamic hashmap are not readily available. We loop through the array to populate this table and again to check for the majority element. This approach uses the offset to handle negative numbers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as we traverse the array twice, Space Complexity: O(n) since we use an additional data structure to store 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.
Boyer-Moore works by selecting a potential candidate and adjusting a counter up and down as it processes the list. If the counter becomes zero, a new candidate is considered. The majority presence guarantees the candidate is correct.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as it traverses the array once, Space Complexity: O(1) because no extra space is used except for variables.
| Approach | Complexity |
|---|---|
| HashMap Counting Approach | Time Complexity: O(n) as we traverse the array twice, Space Complexity: O(n) since we use an additional data structure to store counts. |
| Boyer-Moore Voting Algorithm | Time Complexity: O(n) as it traverses the array once, Space Complexity: O(1) because no extra space is used except for variables. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting | O(n) | O(n) | General case when simplicity matters and extra memory is acceptable |
| Sorting | O(n log n) | O(1) or O(log n) | Useful when the array is already being sorted or implementation simplicity is preferred |
| Boyer-Moore Voting Algorithm | O(n) | O(1) | Best interview solution when the problem guarantees a majority element |
Majority Element I | Brute-Better-Optimal | Moore's Voting Algorithm | Intuition 🔥|Brute to Optimal • take U forward • 437,679 views views
Watch 9 more video solutions →Practice Majority Element with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor