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: Given an integer array nums, return the element that appears more than ⌊n/2⌋ times. The problem guarantees that a majority element always exists, so at least one value occurs in more than half of the positions in the array.
Approach 1: HashMap Counting (O(n) time, O(n) space)
This approach uses a frequency map to count how many times each value appears. Iterate through the array and update counts in a hash table. As soon as a count exceeds n/2, return that number. Hash lookups and updates run in constant time on average, so the full scan remains linear. This approach is straightforward and easy to reason about, especially if you're already comfortable with hash tables and frequency counting patterns.
Approach 2: Sorting (O(n log n) time, O(1) space)
Sorting the array reveals a useful property of majority elements. If a number appears more than half the time, it must occupy the middle index after sorting. Sort the array and return the element at index n/2. This works because the majority element dominates the center of the sorted order. The tradeoff is the O(n log n) cost of sorting. This approach can still be practical when sorting utilities are readily available and memory use must remain minimal.
Approach 3: Boyer-Moore Voting Algorithm (O(n) time, O(1) space)
The Boyer-Moore Voting Algorithm is the optimal solution. It scans the array once while maintaining a candidate and a count. When the count drops to zero, the current element becomes the new candidate. Matching elements increase the count, while different elements decrease it. Because the majority element appears more than half the time, it cannot be fully canceled out by other values. After one pass, the candidate must be the majority element. This technique relies purely on counters and sequential iteration, making it extremely space efficient. It is a classic pattern when working with arrays and majority detection problems.
Recommended for interviews: The Boyer-Moore Voting Algorithm is what most interviewers expect. It demonstrates understanding of algorithmic optimization and achieves the best possible complexity: O(n) time and O(1) space. Starting with a HashMap explanation shows clear thinking about counting, but transitioning to Boyer-Moore shows stronger problem-solving ability. Some candidates also mention the divide and conquer perspective, but Boyer-Moore remains the most common optimal answer.
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.
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.
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 and clarity matter |
| Sorting | O(n log n) | O(1) or O(log n) | Useful when sorting is already required or memory must stay minimal |
| Boyer-Moore Voting Algorithm | O(n) | O(1) | Best interview solution with optimal time and constant space |
Majority Element - Leetcode 169 - Python • NeetCode • 171,922 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