Majority Element Easy 0 attempts
LeetCode ↗

Majority Element

Easy ArrayTwo Pointers LeetCode

Given an array nums of size n, return the majority element — the element that appears more than ⌊n / 2⌋ times. You may assume the majority element always exists.

Since the majority element occurs more than half the time, it's guaranteed to be unique.

Examples

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

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

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
Sample Input
nums = [3,2,3]
Sample Output
3
Constraints
  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
Test Cases
Case 1
Args: [[3,2,3]] Expected: 3
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.

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