To solve the problem of finding the majority element (if it exists), we need to understand what 'majority' means in this context. A majority element is the one that occurs more than n/2 times in the array, where n
is the total number of elements.
Different Situations to Consider
- Case 1: A clear majority element exists
For example, in the array [3, 3, 3, 2, 3, 3], the number 3 appears more than half the time. So it is the majority element and should be returned.
- Case 2: No element appears enough times
In an array like [1, 2, 3, 4], each number appears only once. Since none appear more than n/2 times, the result should be -1
.
- Case 3: Single-element array
If the array has just one element, like [7], that element is automatically the majority because it satisfies the condition (appearing more than n/2 = 0.5 → at least once).
- Case 4: Empty array
An empty array has no elements, so clearly there is no majority. We return -1
.
- Case 5: Two or more elements with equal counts
If the array has balanced occurrences (e.g., [1, 1, 2, 2, 3, 3]), no one element crosses the majority threshold. Again, return -1
.
How Does the Boyer-Moore Voting Algorithm Help?
The Boyer-Moore Voting Algorithm is a clever trick that helps us find the majority element in just one pass using constant space. Here's the core idea:
We keep a candidate
and a count
. Initially, count is 0. As we scan the array:
- If count is 0, we choose the current element as a new candidate.
- If the current element equals the candidate, we increase the count.
- If it does not match, we decrease the count.
By the end of the loop, the candidate is the majority element if one exists. (You can optionally verify it in a second pass.)
Why This Works
When there is a majority element, the increment and decrement of the count cancel out the influence of non-majority elements. The real majority will always survive this cancellation and remain as the candidate.
This method works in O(n) time and O(1) space, which is optimal for this problem.