Majority Element

Easy Arrays & Hashing Moore's Voting Algorithm Original on LeetCode

Majority Element is a easy arrays & hashing problem solved with the moore's voting algorithm pattern. The best approach, optimal (boyer–moore voting), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force (hash map count) up.

Problem

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

Follow-up: can you do it in linear time with constant extra space?

Examples

Example 1

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

Example 2

Input: nums = [2, 2, 3, 3, 3, 2, 2]
Output: 2
Why: 2 appears 4 times out of 7, which is more than 7 / 2.

Constraints

1 <= nums.length <= 5 * 10^4
A majority element always exists.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force (hash map count)	`O(n)`	`O(n)`
Optimal (Boyer–Moore voting)	`O(n)`	`O(1)`

1Brute force (hash map count)

TimeO(n)One pass to count, one pass over the map.

SpaceO(n)Up to n distinct keys.

Count every value with a hash map and return the one whose count is above n / 2.

Count occurrences in a map.
Return the key with count > n / 2.

Java

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        for (Map.Entry<Integer, Integer> e : count.entrySet())
            if (e.getValue() > nums.length / 2) return e.getKey();
        return -1;
    }
}

2Optimal (Boyer–Moore voting)

TimeO(n)A single pass.

SpaceO(1)One candidate and one counter.

Keep one candidate and a counter. A matching value adds a vote, a different value cancels one. The majority value has more votes than all others combined, so it is the candidate left standing.

Start with count = 0.
When count is 0, take the current value as the candidate.
Add 1 if the value equals the candidate, otherwise subtract 1.
Return the candidate.

Java

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;
    }
}

Edge cases to test

Single element
The majority element is not the first element

Hints

Hint 1

If you pair each majority element with a different element and remove both, what is left?

FAQ

What is the best time complexity for Majority Element?

Optimal (Boyer–Moore voting) runs in O(n) time and O(1) extra space. A single pass.

Which pattern does Majority Element use?

It is a arrays & hashing problem that uses the moore's voting algorithm pattern. Other problems with the same pattern: Majority Element II.

Is there a brute force solution for Majority Element?

Yes. Brute force (hash map count) takes O(n) time and O(n) space. Count every value with a hash map and return the one whose count is above n / 2.

Which edge cases should I test for Majority Element?

Single element; The majority element is not the first element.