Coding problem · Easy · Basics

Majority Element

Easy Algorithms & data structures

Return the majority element of nums: the value that appears more than n / 2 times. One always exists.

Example 1

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

Example 2

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

Hints

Hint 1

Counting with a hash map works.

Hint 2

For O(1) space, try Boyer-Moore voting: keep a candidate and a counter that goes up for matches and down for others.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Boyer-Moore voting: when the counter is 0, take the current value as the candidate; matching values add 1, others subtract 1. The majority survives because it outnumbers all other values combined.

Reference solution

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

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

def majority_element(nums: list[int]) -> int:
    candidate, count = 0, 0
    for n in nums:
        if count == 0:
            candidate = n
        count += 1 if n == candidate else -1
    return candidate

<?php

function majorityElement(array $nums): int
{
    $candidate = 0;
    $count = 0;
    foreach ($nums as $n) {
        if ($count === 0) {
            $candidate = $n;
        }
        $count += $n === $candidate ? 1 : -1;
    }
    return $candidate;
}

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int n : nums) {
            if (count == 0) candidate = n;
            count += n == candidate ? 1 : -1;
        }
        return candidate;
    }
}

Was this page helpful?