Majority Element
Problem Description
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:
Example 2:
Constraints:
- n == nums.length
- 1 <= n <= 5 * 104
- -109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in O(1) space?
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute-force method checks each element in the array and counts how many times it appears. If any element occurs more than n/2 times (where n is the length of the array), that element is the majority element.
This approach is simple to understand but inefficient because it performs a full scan for every element.
Code:
- Time Complexity: O(n^2) because for each element, we are iterating through the list to count occurrences.
- Space Complexity: O(1) because no extra space is used aside from variables.
2. HashMap
Intuition:
We can optimize the brute force approach by using a HashMap to store the frequency of each element.
Traverse the array, and increment the counter for each element encountered. The element with a frequency greater than n/2 will be the majority element.
Code:
- Time Complexity: O(n) because we iterate over the array once.
- Space Complexity: O(n) because we might store all elements in the map in the worst case.
3. Sorting
Intuition:
If we sort the array, all identical elements naturally group together. Since the majority element appears more than n/2 times, it must occupy the entire middle region of the sorted array.
That means the element at index n/2 will always be the majority element.
Code:
- Time Complexity: O(n log n) due to sorting.
- Space Complexity: O(1) when using in-place sorting (ignoring input space).
Example Walkthrough:
Input:
After sorting:
4. Boyer-Moore Voting Algorithm
Intuition:
The Boyer-Moore Voting Algorithm efficiently finds the majority element in linear time.
It maintains:
- candidate: current guess for the majority
- count: confidence in the candidate
As you scan:
- If
count == 0, adopt the current number as the newcandidate. - If the current number equals
candidate, incrementcount; otherwise, decrement it.
If a true majority exists, this process guarantees the final candidate is that majority.
Why does it work?
Think cancellation. Pair up elements as we scan:
- Each time we see a value different from the current
candidate, we “cancel” one occurrence of the candidate with that different value by doingcount--. - Each time we see the same value as the candidate, we increase
count, effectively “uncanceling” or reinforcing the candidate.
If there truly is a majority element M (appears more than ⌊n/2⌋ times), then:
- Across the entire array, every non-
Melement can be paired with at most oneMfor cancellation. - Since
Moccurs strictly more than all others combined, you cannot cancel all of theMs. There will be a surplus ofMs left unpaired. - That surplus ensures the final surviving candidate is
M.
Code:
- Time Complexity: O(n) since it passes through the array once.
- Space Complexity: O(1) since only a few additional variables are used.