Majority element (> n/2 times)

Easy

Problem

Return the element that appears more than n/2 times, or −1 if no such element exists. Aim for O(n) time and O(1) space.

Example 1

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

Example 2

Input:  [3, 1, 3, 3, 2]
Output: 3

Also asked as: find majority element

Test cases

Case 1

Input:    [2,2,1,1,1,2,2]
Expected: 2

Case 2

Input:    [3,1,3,3,2]
Expected: 3

Case 3

Input:    [1,1,2,2]
Expected: -1

Case 4

Input:    [1,2,3]
Expected: -1

Case 5

Input:    [1]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Boyer–Moore voting

Time O(n)Space O(1)

Keep a candidate and a count; +1 on a match, −1 otherwise; reset the candidate when count hits 0. A final scan verifies.

function majorityElement(a) {
let cand = null, count = 0;
for (const x of a) {
if (count === 0) cand = x;
count += x === cand ? 1 : -1;
}
return a.filter((x) => x === cand).length > a.length / 2 ? cand : -1;
}