Majority Element

Examples

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

3 appears twice out of three elements - more than half.

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

2 appears 4 times out of 7, which is more than half.

Input: nums = [1]
Output: 1

Constraints

• 1 <= nums.length <= 5 * 10^4

• A majority element (appearing more than n/2 times) always exists.

Approach

The straightforward approach is to count how often each number appears using a hash map, and return the one whose count passes n/2.

There's a cleverer approach, known as the Boyer-Moore voting idea, that needs no extra memory at all. Think of it as a tug-of-war: keep a "candidate" and a counter starting at zero. Walk through the list - if the counter is zero, adopt the current number as the new candidate. Then add 1 to the counter if the current number matches the candidate, or subtract 1 if it doesn't. Because the true majority element outnumbers everything else put together, it can never be fully cancelled out by the time you reach the end, so whatever candidate remains is the answer.

Solutions

Brute Force - Count With a Hash Map

Count how many times each number appears using a hash map. As soon as any number's count passes n/2, return it.

function majorityElement(nums) {
  const counts = new Map();
  const majorityThreshold = Math.floor(nums.length / 2);

  for (const num of nums) {
    counts.set(num, (counts.get(num) || 0) + 1);
    if (counts.get(num) > majorityThreshold) {
      return num;
    }
  }
}

Time: O(n) · Space: O(n)

Optimal - Boyer-Moore Voting

Keep a running candidate and a counter, both starting empty. For each number: if the counter is zero, make this number the new candidate. Then increase the counter if the number matches the candidate, or decrease it otherwise. The majority element, by definition, can never be fully cancelled out, so it's guaranteed to be the candidate left standing at the end.

function majorityElement(nums) {
  let candidate = null;
  let count = 0;

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

  return candidate;
}

Time: O(n) · Space: O(1)