Problem 2.2 · ArraysEasy

Majority Element

PatternRunning State in One Pass Frequency Counting

What it teaches: Three answers to one question: counting with a map, sorting, and the Boyer-Moore vote that needs only two variables.

Practise it on judges as “Majority Element”.

The problem

Given an array nums of size n, return the majority element: the value that appears more than n / 2 times. You may assume a majority element always exists.

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 5 × 10⁴
−10⁹ ≤ nums[i] ≤ 10⁹
A majority element always exists

Pattern clues in the wording

→ "Appears more than n/2 times"
→ Counting frequencies would work; the follow-up asks for O(1) space

These clues point to Running State in One Pass: Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        return candidate;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [3,2,3]	3
2	nums = [2,2,1,1,1,2,2]	2
3	nums = [7]	7

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Count with a hash map · O(n)2. Sort and take the middle · O(n log n)3. Optimal: Boyer-Moore voting · O(n)

Count with a hash map

Time O(n) Space O(n)

Count every value; return the one whose count passes n / 2.

Approach 1

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) {
            int c = count.merge(x, 1, Integer::sum);
            if (c > nums.length / 2) return x;
        }
        return -1;   // unreachable: a majority always exists
    }
}

Verdict: Simple and fast, but uses a map that can grow to n/2 entries.

Sort and take the middle

Time O(n log n) Space O(1) extra

A value filling more than half the array must cover the middle index after sorting, whatever its value.

Approach 2

import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

Verdict: Short and clever, but slower and it reorders the input.

Optimal: Boyer-Moore voting

Time O(n) Space O(1)

Keep a candidate and a count. For each value: if count is 0, make it the candidate. Then add 1 if it equals the candidate, otherwise subtract 1.

Each subtraction cancels one candidate vote against one different vote. The majority has more votes than all others combined, so it can't be fully cancelled and is the candidate at the end.

▶ Dry run: Votes cancelling outnums = [2, 2, 1, 1, 1, 2, 2]

↑i

State(vars)

candidate = 2count = 1

Step 1/7Count is 0, so 2 becomes the candidate with count 1.

Approach 3

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

Verdict: One pass, two variables. The expected answer to the O(1)-space follow-up.

Before you submit

Edge cases and common mistakes

Test these inputs

One element
Majority exactly n/2 + 1
Majority values at the end only

Mistakes people make

Using the vote result when a majority isn't guaranteed: then you must verify it with a second counting pass.
Thinking count is the real frequency: it isn't, it's a net vote.

Interview

Follow-up questions

What if a majority element might not exist?

How would you find all elements appearing more than n / 3 times?

Command Palette