Problem editorial

Majority Element

EasyArray/Matrix Manipulation PatternsArrayCountingGreedy

Majority Element: the approach in brief

The problem

Implement Solution.majorityElement(nums), where nums is a non-empty array of integers. Let n be the number of elements in nums; an integer is a majority element when it occurs more than n / 2 times in the array.

Pattern

Majority Element is a Array/Matrix Manipulation Patterns problem, in the Hashing - Frequency Map / Counting subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Approach outline

Track a value that could still be the majority while scanning the array.
When the current value agrees with the candidate, strengthen its support; otherwise, weaken it.
A value paired against a different value can cancel one occurrence of each without changing which value can have more than half of the total occurrences.

Complexity

The reference solution runs in O(n) time and O(1) space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Majority Element and the problems around it

Majority Element is a Array/Matrix Manipulation Patterns problem, in the Hashing - Frequency Map / Counting subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Majority Element