Majority Element

EasyArrays · Voting / Counting🧩 Array Manipulation LeetCode #169 ↗Updated Oct 30, 2026

Problem

You are given an integer array nums of length n. Exactly one value appears more than ⌊n/2⌋ times (the input guarantees it exists). Return that majority value.

Input[3,2,3]Output3

Input[2,2,1,1,1,2,2]Output2

1 ≤ n ≤ 5·10⁴ · -10⁹ ≤ nums[i] ≤ 10⁹ · majority always exists · Follow-up: O(n) time, O(1) space.

Try it yourself

Java

class Solution {
    public int majorityElement(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Pair each majority element with a different element and cancel both out — the majority has more copies than all other values combined, so it is the one left standing.

PatternArray Manipulation

Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.

Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.

Open the Array Manipulation guide →

Approaches

Brute ForceCount Every Candidate

Time O(n²)Space O(1)

Treat each nums[i] as a candidate and count its occurrences with a second scan. The first value whose count exceeds n/2 is the answer.

Java

public int majorityElement(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) count++;
        }
        if (count > n / 2) return nums[i];
    }
    return -1; // unreachable: a majority is guaranteed
}

Trivial and memory-free, but quadratic — too slow for n = 5·10⁴.

BetterHash Map Frequency

Time O(n)Space O(n)

Store each value's running count in a HashMap. As soon as a count passes n/2, return it — one pass, constant-time lookups. (Sorting and returning nums[n/2] also works in O(n log n), since the majority must cover the middle.)

Java

public int majorityElement(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    int n = nums.length;
    for (int num : nums) {
        int c = count.merge(num, 1, Integer::sum);
        if (c > n / 2) return num;
    }
    return -1; // unreachable
}

Linear time, but up to n/2 distinct keys cost O(n) memory.

OptimalBoyer–Moore Voting

Time O(n)Space O(1)

Keep a candidate and a count. A matching value votes +1, a different one votes −1; when count hits 0, the next value becomes the candidate. Each −1 cancels one majority copy against one other copy, and the majority cannot be fully cancelled, so it survives.

Java

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 0;
    for (int num : nums) {
        if (count == 0) candidate = num; // previous block fully cancelled
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

Dry run[2,2,1,1,1,2,2]

i current index changed

i=0,1
2

2
i
1

1

1

2

2

cand=2, cnt=2
i=2,3
2

2

1

1
i
1

2

2

cnt 2→1→0
i=4
2

2

1

1

1
i
2

2

cnt=0 → cand=1, cnt=1
i=5
2

2

1

1

1

2
i
2

2≠1 → cnt=0
i=6
2

2

1

1

1

2

2
i
cand=2, cnt=1 ✔

One pass, two variables — answers the follow-up exactly.

Pro tip

If a majority is not guaranteed, add a second pass that counts candidate and verifies it exceeds n/2.

At a glance

Level	Approach	Time	Space
Brute Force	Count Every Candidate	`O(n²)`	`O(1)`
Better	Hash Map Frequency	`O(n)`	`O(n)`
Optimal	Boyer–Moore Voting	`O(n)`	`O(1)`

Common pitfalls

Using ≥ n/2 instead of > n/2 — wrong for even n.
Switching candidate after decrementing — check count == 0 first.
Assuming the Boyer–Moore result is valid without a guarantee — verify it.

Interview tips

Mention sorting + nums[n/2] as a quick O(n log n) one-liner.
Explain Boyer–Moore as “pairwise cancellation”, not just code.
Extend: Majority Element II (> n/3) keeps two candidates.

Pattern

Boyer–Moore voting → find a value occurring more than n/k times in O(1) extra space.

My notes saved in this browser