Majority Element

Easy· voting· counting

Problem

You are given an array of size n in which one value appears more than n / 2 times. Return that value. Aim for linear time and constant extra space.

Examples

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

Output: 4

4 appears 3 times out of 5, which is more than half.

Input: nums = [6,6,7]

Output: 6

Constraints

• 1 <= n <= 5 * 10^4
• A majority element is guaranteed to exist

Hints & approach

Hint 1

A hash map of counts works, but can you avoid the extra memory?

Hint 2

If you pair each majority occurrence with a different value and cancel them, something always survives.

Hint 3

Track a single candidate and a counter that goes up on a match and down otherwise.

Approachtry the hints first

Use the Boyer-Moore voting algorithm. Keep a candidate and a count. When count is zero, adopt the current value as the candidate; then increment count if the value matches the candidate and decrement it otherwise. Because the majority value outnumbers all other values combined, it cannot be fully cancelled out, so it is the candidate left at the end.

Time O(n) · Space O(1)

← PreviousMove Zeroes Next →Max Consecutive Ones