Watch 10 video solutions for Majority Element, a easy level problem involving Array, Hash Table, Divide and Conquer. This walkthrough by take U forward has 437,679 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |