Majority element (> n/2 times)
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
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;}