15. Majority Element
easyAsked at PalantirGiven 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 Sam K., 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.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9Follow-up: solve in linear time and O(1) space.
Examples
Example 1
nums = [3,2,3]3Example 2
nums = [2,2,1,1,1,2,2]2Example 3
nums = [1]1Approaches
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.
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.