Code Logo

Majority Element

Published at16 Mar 2026
Created by
Easy 27 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.

Edge cases include arrays with all identical elements (the majority is that element) and arrays with exactly n/2 + 1 occurrences of the majority element. The hash map approach handles all cases correctly without special handling.

The majority element always exists by the problem definition, which simplifies implementation. The Boyer-Moore voting algorithm solves this in O(n) time and O(1) space by canceling out different elements, but the hash map approach is easier to understand and implement correctly in an interview setting.

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

Solution Approach

Given an array nums of size n, return the majority element (the element that appears more than floor(n/2) times). Use the Boyer-Moore voting algorithm: maintain a candidate and count. When count reaches 0, pick the current element as the new candidate. This works because the majority element appears more than half the time.

function majorityElement(nums) {
  var candidate = nums[0], count = 1;
  for (var i = 1; i < nums.length; i++) {
    if (count === 0) { candidate = nums[i]; count = 1; }
    else if (nums[i] === candidate) count++;
    else count--;
  }
  return candidate;
}

Iterate through the array. If count is 0, set the current element as the new candidate. If the current element matches the candidate, increment count; otherwise decrement it. The surviving candidate after one pass is the majority element.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Map<Integer,Integer> counts = new HashMap<>();
        int half = nums.length / 2;
        for (int n : nums) {
            counts.put(n, counts.getOrDefault(n, 0) + 1);
            if (counts.get(n) > half) return n;
        }
        return -1;
    }
}