169. Majority Element

At a Glance

• Topic: Array
• Pattern: Boyer-Moore
• Difficulty: Easy
• LeetCode: 169

Problem Statement

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

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

Constraints:

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
The input is generated such that a majority element will exist in the array.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Approach & Solution Steps

Use the Boyer-Moore Voting Algorithm. Maintain a candidate and a count. If count is 0, update candidate. If current element matches candidate, increment count; otherwise, decrement.

Optimal JS Solution

function majorityElement(nums) {
  let candidate = null, count = 0;
  for (const num of nums) {
    if (count === 0) candidate = num;
    count += (num === candidate ? 1 : -1);
  }
  return candidate;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.