1. The Problem
Given an array `A` of `n` integers, find an element `x` that appears more than n/2 times. If no such element exists, report that.
2. O(n log n) Algorithm (Sorting)
Idea: If a majority element exists, it must be the median of the array after sorting.
- Sort the input array `A`. This takes O(n log n) time.
- The element at the middle index, `candidate = A[floor(n/2)]`, is the only possible majority element.
- Perform a second pass through the array to count the occurrences of `candidate`. This takes O(n) time.
- If the count is greater than `n/2`, `candidate` is the majority element. Otherwise, none exists.
Complexity Analysis
- Time: O(n log n)
- Dominated by the initial sorting step.
- Space: O(1) or O(log n)
- Depends on the in-place nature of the sort implementation.
3. O(n) Algorithm (Boyer-Moore Voting)
Idea: This is a more efficient, linear-time algorithm. It works by maintaining a `candidate` and a `count`. We iterate through the array, incrementing the count if we see the candidate, and decrementing if we see a different element. When the count hits zero, we pick a new candidate. The key insight is that the majority element will always "survive" this process of elimination.
- First Pass (Find Candidate):
- Initialize `candidate = null` and `count = 0`.
- Iterate through `A`. If `count` is 0, set `candidate` to the current element and `count` to 1. If the current element matches `candidate`, increment `count`; otherwise, decrement `count`.
- Second Pass (Verify Candidate):
- The `candidate` from the first pass is our only possibility. Reset a counter to 0.
- Iterate through `A` again. Count the actual occurrences of `candidate`.
- If the count is greater than `n/2`, return `candidate`. Otherwise, no majority element exists.
Complexity Analysis
- Time: O(n)
- Two linear passes through the array.
- Space: O(1)
- Only requires a few variables for storage.