Easy
ArrayHash TableDivide and ConquerSortingCounting
Updated Sep 2026

Majority Element

Asked at Google, Amazon, Oracle

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.

Asked At

CompanyDifficulty
GoogleEasyView all Google questions →
AmazonEasyView all Amazon questions →
OracleEasyView all Oracle 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.

Visual walkthrough for [2, 2, 1, 1, 1, 2, 2]:
candidate=2, count=1
2==2, count=2
1!=2, count=1
1!=2, count=0
count==0, candidate=1, count=1
1==1, count=2
1!=2? No, 1==1. Wait, element is 2. 2!=1, count=1.
Actually let me retrace: [2,2,1,1,1,2,2]
2: candidate=2, count=1
2: count=2
1: count=1
1: count=0
1: candidate=1, count=1
2: count=0
2: candidate=2, count=1
Final candidate = 2. Correct!

6.

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).

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

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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask Majority Element?

Majority Element is asked at Google, Amazon, Oracle. 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.