Majority Element

Is Subsequence

Plus One

Find the element that appears more than half the time in an array.

Given an array `nums` of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

**Examples**
1. `nums = [3, 2, 3]` returns `3`.
2. `nums = [2, 2, 1, 1, 1, 2, 2]` returns `2`.

**Constraints**
- `n == nums.length`
- `1 <= n <= 5 * 10^4`
- `-10^9 <= nums[i] <= 10^9`
- The majority element is guaranteed to exist.

## Follow up
Could you solve the problem in linear time and in O(1) space? (Hint: Boyer-Moore voting algorithm.)

- 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.

Understand the Majority Guarantee

- 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.

Start with Counting

- 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.

Use Boyer-Moore Voting

- 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.

Update Candidate and Votes

- 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.