Majority Element

Easy Problem 5 of 151 Java and Python

Practice on LeetCode

Problem

Given an array nums of size n, return the majority element: the value that appears more than ⌊n / 2⌋ times.

You may assume the 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
Why: 2 appears 4 times out of 7.

Constraints

1 ≤ n ≤ 5 × 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Explanation

Counting every value works but needs a map. The Boyer–Moore trick: pair each majority element with a different element and cancel them out. Because the majority has more than half the elements, it is the only value that can survive the cancelling.

Approach 1 · Naive

Count with a hash map

Time O(n)
Space O(n)

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

For each number, increment its count in a map.
As soon as a count exceeds n / 2, return that number.

Java

import java.util.*;

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

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if count[num] > len(nums) // 2:
                return num
        return -1

Approach 2 · Optimal

Boyer–Moore voting

Time O(n)
Space O(1)

Keep a candidate and a counter. A matching number votes for the candidate, a different number votes against it. When the counter hits zero, the next number becomes the candidate.

Start with count = 0.
For each number: if count == 0, make it the candidate.
Add 1 to count if the number equals the candidate, otherwise subtract 1.
The candidate left at the end is the majority element.

Java

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

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate, count = 0, 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

Complexity compared

Approach	Time	Space
Naive Count with a hash map	O(n)	O(n)
Optimal Boyer–Moore voting	O(n)	O(1)

Key takeaways

Boyer–Moore only works because the majority is guaranteed. If it might not exist, make a second pass to count the candidate.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem