Problem statement

Given an array nums of size n, return the majority element — the element that appears more than n / 2 times. It always exists in the input.

Example 1

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

Example 2

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

Constraints

• 1 <= nums.length <= 31
• -100 <= nums[i] <= 100
• The majority element always exists.

Follow-up: Boyer–Moore voting solves it in O(n) time and O(1) space.

Hints for Majority Element

1. Hint 1

   Counting occurrences with a hash map works in one pass.

2. Hint 2

   Boyer–Moore: keep a candidate and a counter; matching elements vote up, others vote down.

How to solve Majority Element

The Boyer–Moore voting algorithm. Hold a candidate and a counter. Each element that matches the candidate votes for it; each element that differs votes against. When the counter hits zero the candidate is replaced. Because the majority element occupies more than half the array, it is the only value that can survive.

Approach

1. Start with no candidate and a count of 0.
2. For each element: if the count is 0, adopt it as the candidate.
3. Increment the count when the element equals the candidate, decrement it otherwise.
4. The candidate left at the end is the majority element.

Why it works

Think of it as pairing off each majority occurrence against one non-majority occurrence and cancelling both. Since the majority strictly exceeds n / 2, there are not enough other elements to cancel them all, so at least one majority occurrence survives every possible pairing — and the algorithm's counter is exactly a running tally of that cancellation. Because the problem guarantees a majority exists, no verification pass is needed; without that guarantee, a second pass would have to confirm the candidate.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Replace the candidate only when the count reaches zero, not on every mismatch.
• The guarantee that a majority exists is what makes a single pass enough; drop it and the result is merely a candidate.
• Sorting and taking the middle element also works and is easy to reason about, but costs O(n log n).
• "More than n / 2" is strict — exactly half is not a majority.

Reference solution

Python

from typing import List

def majorityElement(nums: List[int]) -> int:
    count = 0
    cand = nums[0]
    for x in nums:
        if count == 0:
            cand = x
        count += 1 if x == cand else -1
    return cand

Java

public static int majorityElement(int[] nums) {
    int candidate = nums[0], count = 0;
    for (int x : nums) {
        if (count == 0) candidate = x;
        if (x == candidate) count++;
        else count--;
    }
    return candidate;
}

C++

int majorityElement(vector<int>& nums) {
    int candidate = nums[0], count = 0;
    for (int x : nums) {
        if (count == 0) candidate = x;
        if (x == candidate) count++;
        else count--;
    }
    return candidate;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy