Majority Element - Solution & Explanation
Problem Statement
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] <= 109
Follow-up: Could you solve the problem in linear time and in
O(1) space?Approach Overview
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 1: HashMap Counting Approach
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.
Complexity
Time Complexity: O(n) as we traverse the array twice, Space Complexity: O(n) since we use an additional data structure to store counts.
Approach 2: Boyer-Moore Voting Algorithm
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.
Complexity
Time Complexity: O(n) as it traverses the array once, Space Complexity: O(1) because no extra space is used except for variables.
Approach 3: Moore Voting Algorithm
The basic steps of the Moore voting algorithm are as follows:
Initialize the element m and initialize the counter cnt = 0. Then, for each element x in the input list:
- If
cnt = 0, thenm = xandcnt = 1; - Otherwise, if
m = x, thencnt = cnt + 1, otherwisecnt = cnt - 1.
In general, the Moore voting algorithm requires two passes over the input list. In the first pass, we generate the candidate value m, and if there is a majority, the candidate value is the majority value. In the second pass, we simply compute the frequency of the candidate value to confirm whether it is the majority value. Since this problem has clearly stated that there is a majority value, we can directly return m after the first pass, without the need for a second pass to confirm whether it is the majority value.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
Complexity Comparison
| 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. |
| Moore Voting Algorithm | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Majority Element I | Brute-Better-Optimal | Moore's Voting Algorithm | Intuition 🔥|Brute to Optimal • take U forward • 771,610 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Majority Element easy or hard?
Majority Element Python/Java solution
How to solve Majority Element in O(n)?
What is the best approach for Majority Element?
Is Majority Element asked at Google/Amazon/Meta?
What data structure is used in Majority Element?
What is the time complexity of Majority Element?
Ready to solve this problem?
Practice Majority Element with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor