Majority Element

Ishaan S Published 24 Oct, 2026

You are given an integer list nums of length n. One value in it is a majority element: it occupies strictly more than half of the positions, that is, it appears more than ⌊n / 2⌋ times.

Return that value. The input is guaranteed to contain a majority element, so there is always exactly one correct answer.

A hash map makes this straightforward; the interesting challenge is to solve it in linear time while using only a constant amount of extra memory.

Example 1

Input: nums = [6,1,6] Output: 6 Why: 6 appears twice out of three positions, which is more than half.

Example 2

Input: nums = [2,9,9,4,9] Output: 9 Why: 9 appears three times out of five.

Example 3

Input: nums = [-5] Output: -5 Why: A single element is trivially the majority.

Constraints

1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹
A majority element always exists.

Pattern Path · Hashing & Counting · problem 5 of 169

Counting every value with a dictionary works in O(n) time. Can you avoid storing a count for every distinct value?

Imagine pairing up two different values and removing both. Can the majority value ever be wiped out this way?

Keep one candidate and a counter. A matching value increments the counter, a different value decrements it, and when the counter hits zero the next value becomes the new candidate.

Target: O(n) time, O(1) extra space.

Start simple

For each element, count how many times it appears with a second loop and return the first one above n/2: O(n²) time, O(1) space.

The key idea

The Boyer-Moore voting idea: think of every occurrence of the majority as a vote for it and every other element as a vote against it. Because the majority holds more than half of the positions, it has more votes than all other values combined, so it survives any sequence of one-for-one cancellations.

We simulate those cancellations with a candidate and a count. When count is 0, the current element becomes the candidate. An element equal to the candidate adds 1; a different element cancels one vote by subtracting 1.

Every time count drops back to 0, the prefix we just processed can be split into pairs of different values, so at most half of it was the majority. That means the majority still holds more than half of the remaining suffix, and the argument repeats. The candidate left at the end must therefore be the majority.

If the majority were not guaranteed, a second pass to verify the candidate's count would be needed.

Complexity

Time: O(n)
Space: O(1)

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate, count = None, 0
        for x in nums:
            if count == 0:
                candidate = x        # start a new voting round
            count += 1 if x == candidate else -1
        return candidate

JavaScript

var majorityElement = function(nums) {
  let candidate = null;
  let count = 0;
  for (const x of nums) {
    if (count === 0) candidate = x;   // start a new voting round
    count += x === candidate ? 1 : -1;
  }
  return candidate;
};

What the interviewer is checking

The hash-map solution is expected; the interviewer is really checking whether you can find (and justify) the constant-space voting algorithm.

Mistakes to avoid

Resetting the candidate on any mismatch instead of only when the count reaches zero.
Assuming the candidate is valid when the problem does not guarantee a majority (verify with a second pass).
Sorting and returning the first element instead of the middle one.

Follow-ups to expect

What if no majority is guaranteed? (Second pass to verify the count.)
Find every value appearing more than n/3 times. (Two candidates, two counters.)
Can sorting help? (The middle element after sorting, O(n log n).)

In real software

Streaming "heavy hitter" detection, such as spotting the dominant source of traffic in a network or the leading value in a sensor feed, uses the same constant-memory voting idea.

Practice next

Topics #005 #t-hashing Array Easy Hash Table Practice Sorting