Skip to main content

22. Majority Element

easyAsked at Snowflake

Find the element appearing more than n/2 times. Snowflake asks this because Boyer-Moore voting is the canonical O(1)-space streaming algorithm — and similar sketch-based algorithms underpin their approximate aggregation functions.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake stream-team screens use this to set up Misra-Gries sketch follow-up.
  • LeetCode Discuss (2025-09)— Reported at Snowflake new-grad screens.

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 counts

Count occurrences; 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);
  for (const [k, v] of count) if (v > nums.length / 2) return k;
}

Tradeoff: O(n) space. Fine, but misses the O(1) trick.

2. Boyer-Moore voting (optimal)

Maintain a candidate and a count. On match, increment; on mismatch, decrement. When count hits 0, swap candidate.

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) space, single pass, streaming-friendly. The intuition: the majority element survives any cancellation against non-majority elements.

Snowflake-specific tips

Snowflake interviewers love Boyer-Moore because it's the textbook example of a streaming algorithm with constant memory. Bonus signal: pivot to Misra-Gries (generalization to k heavy hitters) and Snowflake's approximate APPROX_TOP_K function, which uses a Space-Saving sketch built on the same principle.

Common mistakes

  • Adding a final verification pass that the candidate really is the majority — only needed if existence isn't guaranteed.
  • Treating count as the number of occurrences rather than a 'lead'.
  • Sorting and returning the middle — O(n log n), works but isn't streaming.

Follow-up questions

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

  • Majority Element II (LC 229) — elements appearing more than n/3 times.
  • Generalized to top-k heavy hitters (Misra-Gries / Space-Saving).
  • How does Snowflake implement APPROX_TOP_K?

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?

If majority > n/2, then for every non-majority element you 'cancel', the majority still has surplus votes left over. The final candidate is guaranteed to be the majority — when it exists.

How does Snowflake APPROX_TOP_K work?

It uses a Space-Saving sketch — generalizes Boyer-Moore to k tracked elements. For each new element, if it's tracked, increment; else replace the min-count tracked with this new element + 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →