Code Logo

Majority Element

Published at16 Mar 2026
Created by
Easy 10 views
Like0

You are given an array where one value is guaranteed to appear more than half of the time. Your job is to return that value.

The phrase more than half is the key rule. If the array has length n, the answer must appear strictly more than n / 2 times. That means it is not just the most frequent number. It appears often enough to outnumber all other values combined.

For example, in [3,2,3], the answer is 3 because it appears 2 times out of 3. In [2,2,1,1,1,2,2], the answer is 2 because it appears 4 times out of 7.

So the task is to count which value crosses the halfway mark and return it.

Example Input & Output

Example 1
Input
nums = [3,2,3]
Output
3
Explanation

3 appears 2 times, more than n/2.

Example 2
Input
nums = [2,2,1,1,1,2,2]
Output
2
Explanation

2 appears 4 times out of 7.

Example 3
Input
nums = [1]
Output
1
Explanation

Only element is majority.

Algorithm Flow

Recommendation Algorithm Flow for Majority Element
Recommendation Algorithm Flow for Majority Element

Solution Approach

A clear hash table solution is to count how many times each number appears, then return the one whose count becomes larger than half the array length.

We start by creating a map where the key is the number and the value is its frequency. Then we walk through the array once. For each number, we increase its count in the map by one. After updating the count, we can immediately check whether that count is now greater than nums.length / 2. If it is, we already found the majority element and can return it right away.

That early check is useful because we do not actually need a second pass. The moment one value crosses the halfway mark, the problem guarantee tells us it must be the answer.

In JavaScript-style pseudocode, the idea is:

const freq = new Map(); const limit = Math.floor(nums.length / 2); for (const num of nums) { const count = (freq.get(num) || 0) + 1; freq.set(num, count); if (count > limit) return num; }

This works because the majority element is guaranteed to exist, so one count will eventually pass the limit. The time complexity is O(n), and the extra space is O(n) in the worst case if many distinct values appear before the winner becomes obvious.

Best Answers

java
import java.util.*;
class Solution {
    public int majority_element(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        int limit = nums.length / 2;
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
            if (freq.get(x) > limit) return x;
        }
        return nums.length > 0 ? nums[0] : 0;
    }
}