Majority Element

Problem

Given an array nums of size n, return the majority element (the value that appears more than n/2 times). Assume a majority element always exists.

Constraints

• 1 ≤ n ≤ 5·10⁴
• majority element is guaranteed to exist

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def majorityElement(self, nums):
        count, cand = 0, None
        for x in nums:
            if count == 0:
                cand = x
            count += 1 if x == cand else -1
        return cand

Java

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        // Hash counting: the majority element appears more than n / 2
        // times, so the first count to cross that bar is the answer.
        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 nums[0]; // a majority is guaranteed — never reached

        // O(1)-space alternative — Boyer-Moore vote: keep a candidate
        // and a counter; +1 when the candidate repeats, -1 otherwise,
        // new candidate when the counter hits 0. The true majority
        // survives because it outnumbers everyone else combined.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.