How do you approach Majority Element?

A simple approach uses a hash map to count frequencies.

What is the time complexity of Majority Element?

Time complexity: O(n) - single pass. Space complexity: O(1) - constant space.

What are common mistakes on Majority Element?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

Sitelet https://gitgood.dev/coding/majority-element

gitGood.dev

← Back to problems

Majority Element

EasyAlgorithms

Description

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than n / 2 times. You may assume that the majority element always exists in the array.

Example 1

Input: nums = [3, 2, 3]

Output: 3

Example 2

Input: nums = [2, 2, 1, 1, 1, 2, 2]

Output: 2

Constraints

- n == nums.length - 1 <= n <= 5 * 10^4 - -10^9 <= nums[i] <= 10^9 - The majority element always exists in the array.

Majority Element: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 7 test cases (4 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

A simple approach uses a hash map to count frequencies.
Can you solve it in O(1) space?
Look up Boyer-Moore Voting Algorithm - it finds the majority element in a single pass with constant space.

The optimal approach

Show the approach: Boyer-Moore Voting Algorithm

Maintain a candidate and a count. For each element:

- If count is 0, set the current element as the candidate.

- If the current element equals the candidate, increment count.

- Otherwise, decrement count.

The majority element will always survive this process because it appears more than n/2 times.

Time: O(n) - single pass
Space: O(1) - constant space

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.