EasyArrayHash TableDivide and ConquerSortingCountingUpdated Sep 2026

169. Majority Element

Asked at Google, Amazon, Oracle, Bloomberg

Difficulty

Easy

Time

O(n)

Space

O(1)

Pattern

Array

Companies

4

Problem

You are given an array of integers nums with n elements. One value in the array appears more than n / 2 times. That value is called the majority element. Return it.

You can assume such an element always exists, so you never have to handle the case where no answer exists. There is only one possible answer: two different values cannot both appear more than half the time.

The easy solution is to count every value in a hash map, but that costs O(n) extra space. The follow-up asks for linear time and constant extra space, which is what the Boyer-Moore voting algorithm gives you.

More than half the array

22111220123456The four green cells all hold 2 — that is more than 7 / 2
In [2,2,1,1,1,2,2] the value 2 fills 4 of the 7 slots, which is more than half, so it is the answer.

Constraints

  • ●n == nums.length
  • ●1 <= n <= 5 * 10^4
  • ●-10^9 <= nums[i] <= 10^9
  • ●The input always contains a majority element

Examples

Example 1
Inputnums = [3,2,3]
Output3
Whyn = 3, so more than 1.5 means at least 2 times. The value 3 appears twice, and 2 appears once, so 3 is the majority element.
Example 2
Inputnums = [2,2,1,1,1,2,2]
Output2
Whyn = 7, so more than 3.5 means at least 4 times. The value 2 appears 4 times and 1 appears 3 times, so 2 wins.

Asked At

4 companies
CompanyDifficulty
GoogleEasyView all Google questions →
AmazonEasyView all Amazon questions →
OracleEasyView all Oracle questions →
BloombergEasyView all Bloomberg questions →

How to Think About It

1

Hash table approach: count occurrences of each element in a hash map. Return the element whose count > n / 2. Time: O(n), space: O(n). Works but uses extra space.

2

Sorting approach: sort the array. The majority element will always be at index n / 2 after sorting (it occupies more than half the positions). Time: O(n log n), space: O(1) or O(n) depending on sort.

3

Boyer-Moore Voting Algorithm (optimal): maintain a candidate and a count. For each element:

  • If count == 0, set candidate = current element.
  • If current == candidate, increment count.
  • Else decrement count.
    At the end, candidate is the majority element. Time: O(n), space: O(1).
4

Why Boyer-Moore works: the majority element has > n/2 occurrences. Every time a non-majority element "cancels" one occurrence, there are still majority elements left. The majority element survives because it has more than half the votes.

5

Time: O(n) with one pass. Space: O(1). The Boyer-Moore algorithm is the optimal solution and the one interviewers expect.

Optimal Approach

Boyer-Moore Voting:

  1. Initialize candidate = None, count = 0.
  2. For each element num in the array:
    • If count == 0: set candidate = num.
    • If num == candidate: count += 1.
    • Else: count -= 1.
  3. Return candidate.

Walkthrough: [2, 2, 1, 1, 1, 2, 2]

  • num=2: count=0, candidate=2, count=1
  • num=2: match, count=2
  • num=1: mismatch, count=1
  • num=1: mismatch, count=0
  • num=1: count=0, candidate=1, count=1
  • num=2: mismatch, count=0
  • num=2: count=0, candidate=2, count=1
  • Result: 2 (appears 4 times, > 7/2 = 3.5).

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

Boyer-Moore voting

22111220123456iStep 1 — two 2s in a row: candidate = 2, count = 222111220123456iStep 2 — two 1s cancel the votes: count drops 2 → 1 → 022111220123456iStep 3 — count is 0, so 1 becomes candidate, then the lasttwo 2s cancel it and 2 becomes candidate againcount == 0 → candidate = numnum == candidate → count += 1else → count -= 1answer = candidate
A candidate and a counter. Matching values add a vote, different values cancel one vote, and an empty counter lets the current value become the new candidate.
ComplexityTime O(n)Space O(1)One pass over the array with only a candidate value and a counter kept in memory.

What Trips People Up in Real Interviews

1

Implementing Boyer-Moore incorrectly by checking num == candidate before the count == 0 check. The order matters: first update candidate when count is zero, then update count. Reversing these causes the candidate to be overwritten prematurely.

2

Forgetting that the problem guarantees a majority element exists. Without this guarantee, you would need a second pass to verify the candidate actually appears > n/2 times.

3

Using a hash map when the interviewer asks for O(1) space. The hash map solution is O(n) space. Mention it as an alternative, then optimize to Boyer-Moore.

4

Trying to sort and return nums[n/2] without mentioning the O(n log n) time. It works but is suboptimal. Always present sorting first, then optimize to Boyer-Moore for O(n) time and O(1) space.

5

Not handling the edge case of a single-element array. Boyer-Moore handles it correctly (count=0 sets candidate to that element), but some implementations fail if candidate is initialized to a value outside the array range.

Solution Code

O(n) time
def majorityElement(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1
    return candidate

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Majority Element problem?

Given an array of size n, find 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.

How do you solve Majority Element?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Majority Element?

Majority Element is asked at Google, Amazon, Oracle, Bloomberg. It is a easy difficulty problem.

What are common mistakes on Majority Element?
  • Implementing Boyer-Moore incorrectly by checking `num == candidate` before the `count == 0` check. The order matters: first update candidate when count is zero, then update count. Reversing these causes the candidate to be overwritten prematurely.
  • Forgetting that the problem guarantees a majority element exists. Without this guarantee, you would need a second pass to verify the candidate actually appears > n/2 times.
  • Using a `hash map` when the interviewer asks for `O(1)` space. The `hash map` solution is `O(n)` space. Mention it as an alternative, then optimize to Boyer-Moore.
  • Trying to sort and return `nums[n/2]` without mentioning the `O(n log n)` time. It works but is suboptimal. Always present sorting first, then optimize to Boyer-Moore for `O(n)` time and `O(1)` space.
  • Not handling the edge case of a single-element array. Boyer-Moore handles it correctly (count=0 sets candidate to that element), but some implementations fail if `candidate` is initialized to a value outside the array range.