Majority Element Easy 0 attempts
LeetCode ↗

Majority Element

Easy ArrayTwo Pointers LeetCode

You're given an array nums of length n. Return its majority element — the value that shows up more than ⌊n / 2⌋ times. You can assume such an element always exists in the input.

Because it has to appear in more than half the positions, there can only ever be one candidate that qualifies.

Input Format
Implement majorityElement(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [1]
Output
1
Constraints
  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
Test Cases (2)
Case 1
Args: [[3,2,3]] Expected: 3
Case 2
Args: [[1]] Expected: 1
Topics
ArrayTwo Pointers

Boyer-Moore Voting Algorithm. Maintain a candidate and a counter. Walk through the array: if the counter is zero, pick the current element as the new candidate. Increment the counter when the element matches the candidate, decrement otherwise. The majority element always survives because it appears more than half the time.

javascript
function majorityElement(nums) {
  let candidate = nums[0];
  let count = 0;

  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate) ? 1 : -1;
  }

  return candidate;
}

Time: O(n) — single pass. Space: O(1) — only two variables.

Saved in this browser only. Private to you.

JavaScript