Skip to main content

13. Majority Element

easyAsked at Snap

Find the element that appears more than n/2 times. Snap uses this to verify candidates know Boyer-Moore voting, which is the canonical O(1)-space trick.

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

Source citations

Public interview reports confirming this problem appears in Snap loops.

  • Glassdoor (2026-Q1)— Reported in Snap onsite with the Boyer-Moore follow-up explicitly requested.
  • LeetCode Discuss (2025)— Common stream-counting problem at Snap.

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 occurrences, return the key whose count > n/2.

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

Tradeoff: Correct but uses O(n) space. Snap wants Boyer-Moore.

2. Boyer-Moore voting (optimal)

Track a candidate and a counter. For each element, if counter is 0, pick a new candidate. Increment if it matches the candidate, decrement otherwise.

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

Tradeoff: O(1) space using the cancellation principle — every non-majority vote cancels a majority vote, and majority still has surplus.

Snap-specific tips

At Snap, name 'Boyer-Moore voting' explicitly — recruiters note when candidates cite the algorithm by name. Bonus: connect it to streaming heavy-hitter detection, which Snap uses for trending Stories and spam-filtering view-counts.

Common mistakes

  • Resetting the candidate before count drops to 0.
  • Returning count instead of candidate.
  • Forgetting that the problem guarantees a majority — without that guarantee you'd need a verification pass.

Follow-up questions

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

  • Majority Element II — elements appearing more than n/3 times (LC 229).
  • What if you can't assume a majority exists? Add a verification pass.
  • Streaming Misra-Gries algorithm — generalization to top-k heavy hitters.

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 without a verification pass?

Because the problem guarantees a majority. Every non-majority element can at most pair off one majority vote; since majority has > n/2 votes, surplus survives.

Does sorting work?

Yes — the majority element will be at index n/2 after sort. O(n log n) and not constant-space, but it's a valid baseline.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →