core12 min

Majority Element (Boyer-Moore)

Majority Element

Given an array nums where one element appears more than ⌊n/2⌋ times, return that element. A hash-map count works, but the elegant O(1)-space answer is the Boyer-Moore voting algorithm: keep a candidate and a count; matching votes increment, differing votes decrement, and a zero count adopts a new candidate.

majorityElement([3, 2, 3]);             // 3
majorityElement([2, 2, 1, 1, 1, 2, 2]); // 2

Your code

Results

Run your code to see results.

Stuck? This challenge exercises:

javascript.data-structures