AlgoInsight

Q&A

How to find the majority element in an array

By AlgoInsight Team2026-06-07algorithmsarraysdata-structures

Overview

Given an array where one element appears more than half the time, find it. Because a true majority element occupies over 50% of the array, it has a special property: it survives a "voting" process where each different element cancels it out. That insight powers the elegant Boyer–Moore algorithm.

graph TD
    A[Array] --> B{Approach}
    B --> C[HashMap: count each, O(n) time / O(n) space]
    B --> D[Sort: middle element is majority, O(n log n)]
    B --> E[Boyer-Moore Voting: O(n) time / O(1) space ⭐]
    style E fill:#1e1b4b,color:#fff

Approach 1: Hash Map (intuitive)

Count occurrences; return the one exceeding n/2.

public int majorityElement(int[] nums) {
    Map<Integer, Integer> counts = new HashMap<>();
    int n = nums.length;
    for (int num : nums) {
        int c = counts.merge(num, 1, Integer::sum);
        if (c > n / 2) return num;
    }
    return -1;   // no majority (if guaranteed to exist, won't reach here)
}

O(n) time, O(n) space.

Approach 2: Sorting

If a majority element exists, after sorting it must occupy the middle index n/2 (it spans more than half the positions).

Arrays.sort(nums);
return nums[nums.length / 2];

O(n log n) time, O(1) extra space (ignoring sort's space).

Approach 3: Boyer–Moore Voting (optimal) ⭐

Maintain a candidate and a count. Walk the array: when count is 0, adopt the current element as the candidate; increment count if the element equals the candidate, else decrement. The majority element survives because every non-majority element can cancel at most one majority occurrence, and the majority has more than half.

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;       // pick a new candidate
        }
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

O(n) time, O(1) space - a single pass, two variables.

Why it works (intuition)

Imagine each majority element as +1 and every other element as −1. Because the majority appears more than n/2 times, the running tally can't be fully canceled by the minority - the candidate left standing must be the majority. Pairs of (majority, non-majority) cancel; the surplus majority elements remain.

Trace example

Array: [2, 2, 1, 1, 1, 2, 2]

num=2 count0→candidate=2,count=1
num=2 count=2
num=1 count=1
num=1 count=0
num=1 count0→candidate=1,count=1
num=2 count=0
num=2 count0→candidate=2,count=1
→ candidate = 2  (correct; 2 appears 4 of 7 times)

Verifying a Majority Actually Exists

Boyer–Moore assumes a majority exists. If it might not, do a second pass to confirm the candidate truly exceeds n/2:

int c = 0;
for (int num : nums) if (num == candidate) c++;
return (c > nums.length / 2) ? candidate : -1;

Extension: Majority > n/3 (Boyer–Moore generalization)

For "appears more than ⌊n/3⌋ times," there can be at most two such elements; the voting algorithm generalizes to track two candidates and counters - a common follow-up question.

Why This Matters in Interviews

This is a classic. Interviewers want you to progress from the obvious hash-map solution to the optimal Boyer–Moore voting algorithm and explain why it works (cancellation argument). Mentioning the verification pass (when majority isn't guaranteed) and the n/3 generalization signals strong algorithmic depth.

Common Pitfalls

References

More answers