📖 5 min read
Last updated on

Majority Element — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer says: “Given an array, find the element that appears more than n/2 times.” You recognize it. LeetCode #169. You know the hash map solution takes five minutes. But then comes the follow-up: “Can you do it in O(1) space?” If you know Boyer-Moore Voting, this is a great moment. If you don’t, it’s a hard one to derive under pressure. Majority Element is used precisely because it separates candidates who know multiple solutions from those who stop at the first correct one.

The Problem

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 the majority element always exists in the array.

(LeetCode #169)

Example 1

Input nums = [3, 2, 3]

Output 3

Example 2

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

Output 2

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Multiple solutionsDo you know the hash map, sort, and Boyer-Moore approaches?
The voting algorithmCan you explain why Boyer-Moore is correct without memorizing it?
Trade-off articulationDo you compare O(n)/O(n) vs. O(n log n)/O(1) vs. O(n)/O(1) deliberately?
Guarantee exploitationDo you use the “majority always exists” guarantee to your advantage?
Code clarityIs your Boyer-Moore implementation readable?

Step 1: Clarifying Questions

1. Is the majority element guaranteed to exist? Yes — the problem guarantees it. This is critical: Boyer-Moore only works correctly under this guarantee.

2. Can there be multiple elements appearing > n/2 times? No — only one element can exceed 50% of the array. This is a mathematical fact.

3. Can the array be empty? No — the problem guarantees at least one element.

4. Are values bounded? Not in a useful way. Can’t use a fixed-size array. Hash map or Boyer-Moore both handle arbitrary values.

Step 2: Multiple Approaches

Option A — Hash map (O(n) time, O(n) space): Count frequencies, return the element with count > n/2.

Option B — Sort (O(n log n) time, O(1) space): Sort the array. The majority element must occupy the middle index n//2.

Option C — Boyer-Moore Voting (O(n) time, O(1) space): The optimal solution. Works by cancellation.

Step 3: The Key Insight

Boyer-Moore Voting Algorithm: think of each non-majority element as “canceling” one occurrence of the majority element. Since the majority appears more than n/2 times, it can never be fully canceled — it always survives. Maintain a candidate and a count. When count hits 0, switch to a new candidate. Whatever survives at the end is the majority element.

The proof: the majority element contributes more +1s than any other element contributes -1s to its count. It will always be the last candidate standing.

Step 4: Optimal Strategy (Boyer-Moore)

  1. Initialize candidate = None, count = 0.
  2. For each number:
    • If count == 0, set candidate = num.
    • If num == candidate, increment count.
    • Otherwise, decrement count.
  3. Return candidate.

Python Implementation

Hash map approach:

from collections import Counter

def majorityElement_hashmap(nums: list[int]) -> int:
    counts = Counter(nums)
    return max(counts, key=counts.get)

Sorting approach:

def majorityElement_sort(nums: list[int]) -> int:
    nums.sort()
    return nums[len(nums) // 2]

Boyer-Moore Voting (optimal):

def majorityElement(nums: list[int]) -> int:
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    return candidate

The sorting approach works because: if an element appears more than n/2 times, it must occupy position n//2 in a sorted array. Clean and surprising.

Time & Space Complexity

ApproachTimeSpace
Hash mapO(n)O(n)
SortO(n log n)O(1) extra
Boyer-MooreO(n)O(1)

Boyer-Moore is the asymptotically optimal solution on both dimensions.

Common Interview Mistakes

  1. Not knowing Boyer-Moore. The hash map solution is acceptable, but interviewers at top companies expect you to at least know the O(1) space approach exists, even if you can’t derive it on the spot.

  2. Explaining Boyer-Moore without the cancellation intuition. “I track a candidate and decrement count for mismatches” without explaining why it works sounds like memorization. The key insight: the majority element has more votes than all others combined.

  3. Not exploiting the guarantee. If you’re verifying your candidate at the end, you’ve forgotten that the problem guarantees a majority element exists. Verification is unnecessary here.

  4. Forgetting the sort trick. nums[n//2] after sorting is surprisingly clean and worth knowing as an alternative.

  5. Over-engineering with divide and conquer. There’s a D&C solution, but it’s O(n log n) or O(n) with O(log n) space. Not better than Boyer-Moore.

What a Strong Candidate Sounds Like

“I know three approaches. Hash map is O(n) time and space — straightforward. Sort is O(n log n) but O(1) space — the majority element always ends up at index n//2 after sorting. The optimal is Boyer-Moore voting — O(n) time and O(1) space. The intuition: every non-majority element cancels one majority element, but since the majority appears more than n/2 times, it can never be fully canceled. I maintain a candidate and a count; when count hits zero I switch candidates. Whatever’s left is the majority.”

Example Interview Dialogue

Interviewer: Why does Boyer-Moore always return the correct answer?

Candidate: Because the majority element appears more than n/2 times, it contributes more +1s than any combination of other elements contributes -1s to its count. Even in the worst case where all other elements conspire to cancel it, the majority element has enough votes to survive. When count hits zero, we’re effectively ignoring a balanced prefix — and the majority element still dominates the remaining suffix.

Interviewer: What if there’s no majority element?

Candidate: Boyer-Moore would return some candidate, but it might be wrong. The guarantee that a majority exists is what makes the algorithm correct. Without it, you’d need a verification pass — count occurrences of the returned candidate and check if it actually exceeds n/2.

  • Majority Element II (LeetCode #229). Find all elements appearing more than n/3 times. Extension of Boyer-Moore to two candidates.
  • Find the Duplicate Number (LeetCode #287). Related “find the outlier” pattern with different constraints.
  • Single Number (LeetCode #136). Bit manipulation to find the unique element — another O(n)/O(1) trick worth knowing.
  • Contains Duplicate (LeetCode #217). Hash set approach for frequency checking.

Practice This in a Mock Interview

Majority Element is one of those problems where you’re really being tested on how many solutions you know and how well you can explain them. The Boyer-Moore algorithm is hard to derive under pressure if you’ve only read it once. Explaining it fluently — with the cancellation intuition, not just the code — requires practice.

Start a mock interview for Majority Element on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →