Skip to main content

15. Majority Element

easyAsked at Palantir

Given an array of size n, return the element that appears more than n/2 times. Palantir asks this to test whether you know Boyer-Moore voting — an O(1)-space streaming primitive they care about because it generalizes to finding the dominant entity ID across a sharded dataset without a shuffle.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE — asked for both the simple and O(1)-space version.
  • Blind (2025-10)— Tagged with 'Boyer-Moore' as the expected optimal.

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
  • Follow-up: solve in linear time and O(1) space.

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [1]
Output
1

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 freq = new Map();
  const threshold = nums.length / 2;
  for (const n of nums) {
    const c = (freq.get(n) || 0) + 1;
    if (c > threshold) return n;
    freq.set(n, c);
  }
}

Tradeoff: Linear, easy to explain. But O(n) space — fails the follow-up Palantir typically asks for.

2. Boyer-Moore voting

Keep a candidate and a counter. Increment on match, decrement on mismatch; when counter hits 0, pick the current element as the new 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: Linear time, constant space, single pass. The Boyer-Moore name is the signal Palantir is testing for.

Palantir-specific tips

Palantir specifically asks the follow-up O(1)-space version — knowing Boyer-Moore by name is a strong senior signal. Articulate the invariant out loud before coding: pairing one majority element with one non-majority cancels them both, and since majority > n/2, at least one majority element survives uncancelled. Bonus signal: mention that this generalizes to finding all elements appearing > n/3 times (LC 229) with two candidate slots.

Common mistakes

  • Sorting and returning nums[n/2] — works but is O(n log n), violating the follow-up.
  • Incrementing count BEFORE the candidate switch — breaks the invariant.
  • Forgetting the validation pass when the problem doesn't guarantee a majority exists — for this problem it's given, but mention it in the explanation.

Follow-up questions

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

  • Majority Element II (LC 229) — find all elements appearing more than n/3 times.
  • What if the majority guarantee is removed? Add a verification pass.
  • Distributed version: how do you find the majority across N shards without shuffling? (Hint: Boyer-Moore is associative — merge candidates pairwise.)

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?

Each cancellation pairs one majority element with one non-majority element. Since majority count > n/2, there are more majority elements than non-majority, so at least one majority is left uncancelled and ends as the final candidate.

Does this require a validation pass?

Only when the majority isn't guaranteed. The problem here states it always exists, so you can skip the second pass. In production code, always verify.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →