Majority Element – Solution & Complexity
Solution Walkthrough
Step 1: Understand the Majority Guarantee
- A majority element appears more than half of the array length.
- The problem guarantees such an element exists, so the final answer does not need a failure case.
- The challenge is finding it efficiently without counting every value in extra storage.
Step 2: Start with Counting
- A straightforward solution stores how often each number appears.
- As soon as a count becomes greater than
len(nums) // 2, that number is the answer. - This is linear time, but it uses O(n) extra space for the dictionary.
Step 3: Use Boyer-Moore Voting
- Pair each occurrence of a candidate with a different value and cancel both out.
- Because the majority element appears more than all other values combined, it cannot be fully canceled.
- Keep only a current candidate and a vote count.
Step 4: Update Candidate and Votes
- When the vote count is zero, choose the current number as the new candidate.
- Add one vote when the current number matches the candidate.
- Subtract one vote when it differs, representing a cancellation.
Step 5: Final Complete Solution
- The candidate left after all cancellations is the guaranteed majority element.
- Time complexity is O(n) because each number is processed once.
- Space complexity is O(1) because only two variables are stored.
