Majority Element

Problem

You are given an integer array nums that is guaranteed to contain a majority element: a value that occurs strictly more than len(nums) / 2 times. Return that value.

• The array is non-empty and has at most 100,000 elements.
• Values are arbitrary integers, positive or negative.
• A majority element always exists (the algorithm below depends on this guarantee).

Examples

• nums = [8, 5, 8] → 8. It appears 2 of 3 times.
• nums = [4, 7, 7, 4, 7, 7, 4, 7, 7] → 7. Six of nine.
• nums = [-6] → -6. A single element is trivially the majority.

Hints

1. Counting with a hash map works in O(n) time and O(n) space; can you drop the space?
2. Sorting puts the majority element at the middle index, but that costs O(n log n).
3. Pair off each element with a different element and cancel both; the majority survives. This is Boyer-Moore majority voting.