Majority Element — DSA · Engineering Playbook

Majority Element

Boyer-Moore vote — increment count when seeing the candidate, decrement otherwise; reset candidate when count hits 0.

Easy

Time O(n) Space O(1)

LeetCode

May 16, 2026 2 min read

Problem#

The majority element appears more than n / 2 times. Find it. Assume it always exists.

Examples#

[3,2,3] → 3.
[2,2,1,1,1,2,2] → 2.

Constraints#

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

Approach#

Boyer-Moore voting: keep a candidate and a count. For each element, if count is 0, adopt it as candidate. Increment count if equal to candidate, decrement otherwise.

Solution#

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        for (int v : nums) {
            if (count == 0) candidate = v;
            count += (v == candidate) ? 1 : -1;
        }
        return candidate;
    }
};

func majorityElement(nums []int) int {
    candidate, count := 0, 0
    for _, v := range nums {
        if count == 0 {
            candidate = v
        }
        if v == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0
        for v in nums:
            if count == 0:
                candidate = v
            count += 1 if v == candidate else -1
        return candidate

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

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

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

Editorial#

Each non-majority vote pairs off with a majority vote, canceling. Since the majority count strictly exceeds n/2, at least one majority vote remains after pairing — it’s whatever the candidate ends up as. The algorithm needs no extra memory and runs in one pass.

Complexity#

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

Concept revision#

Find All Duplicates in an Array

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#