Skip to main content

22. Majority Element

easyAsked at Vercel

Find the element that appears more than n/2 times. Vercel asks this for Boyer-Moore — the O(1) space trick that finds the consensus item in a stream, useful for their canary deploy 'majority of nodes report healthy' check.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen; Boyer-Moore expected.
  • Blind (2026-Q1)— Mentioned in Vercel runtime engineer screen.

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

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input
nums = [3,2,3]
Output
3

Example 2

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

Approaches

1. Hash map count

Count each element; return the one with count > n/2.

Time
O(n)
Space
O(n)
function majorityElement(nums) {
  const count = new Map();
  for (const n of nums) {
    count.set(n, (count.get(n) || 0) + 1);
    if (count.get(n) > nums.length / 2) return n;
  }
}

Tradeoff: O(n) space. Vercel will ask for the O(1) version.

2. Boyer-Moore voting (optimal)

Maintain a candidate and count. If count is 0, set candidate. If current matches candidate, increment; else decrement. The final candidate is the majority element.

Time
O(n)
Space
O(1)
function majorityElement(nums) {
  let candidate = null;
  let count = 0;
  for (const n of nums) {
    if (count === 0) candidate = n;
    count += (n === candidate) ? 1 : -1;
  }
  return candidate;
}

Tradeoff: O(1) extra space. The intuition: every minority element 'cancels' one majority vote, but because majority > n/2, it always survives the cancellation.

Vercel-specific tips

Vercel grades for the Boyer-Moore insight. Bonus signal: explaining the cancellation intuition out loud, and noting that this only finds a CANDIDATE — if 'majority always exists' isn't guaranteed, you need a second pass to verify. They like when you raise the edge case before they do.

Common mistakes

  • Returning the candidate without verification when the problem doesn't guarantee a majority — yields wrong answers.
  • Resetting candidate to null after count hits 0 — works, but you can leave it; the next iteration handles it.
  • Confusing '> n/2' with '>= n/2' — strict majority matters.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Majority Element II (LC 229) — elements appearing > n/3 times. Two candidates.
  • Find all elements appearing more than n/k times — k-1 candidates.
  • Streaming version with bounded memory.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Boyer-Moore work?

Imagine every non-majority element 'cancels' one majority vote. Since the majority appears > n/2 times, there are more majority votes than total non-majority votes, so the majority always wins the cancellation.

What if no majority exists?

Then Boyer-Moore returns SOME candidate, but it might be wrong. Add a second pass to verify count > n/2 before returning.

Practice these live with InterviewChamp.AI

Drill Majority Element and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →