Majority Element

The key idea

The majority element appears more than half the time, so if you pair off every occurrence of one value against a different value, the majority always has leftovers. Boyer-Moore voting keeps one running candidate and a count: a matching vote raises the count, a different vote lowers it, and when the count hits zero the next element becomes the new candidate. The true majority survives this cancellation.

Problem

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.

Constraints

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

Examples

Input: nums = [3,2,3] Output: 3

Input: nums = [2,2,1,1,1,2,2] Output: 2

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →