167. Majority Element
You are given an integer array nums of length n. One value in it is a majority element: it occurs strictly more than n / 2 times (using real division — so in an array of 7 elements it appears at least 4 times). Return that value.
Every input is guaranteed to contain a majority element, so you never need to report "none".
Counting occurrences with a hash map gets you there in linear time and linear memory. The famous follow-up: can you find it in O(n) time and O(1) space?
Example 1:
Input: nums = [3, 2, 3]
Output: 3
Explanation: 3 appears twice in an array of length 3, and 2 > 3/2.
Example 2:
Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: 2 appears 4 times out of 7 — more than half.
Constraints:
- 1 ≤ nums.length ≤ 5 * 10⁴
- -10⁹ ≤ nums[i] ≤ 10⁹
- A majority element (count > n/2) always exists.
Hints:
The direct route: tally every value in a hash map and return the one whose count exceeds n/2. Linear time, but linear memory too.
If the array were sorted, where would an element occupying more than half the slots be forced to sit? Look at index n/2.
Boyer–Moore voting: keep one candidate and a counter. Matching elements vote it up, differing elements vote it down, and at zero you adopt the current element as the new candidate. Pairing off one majority vote against one minority vote can never exhaust the majority — it has votes to spare.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 2, 3]
Expected output: 3