Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the element appearing more than ⌊n/2⌋ times. The intuitive answer counts frequencies in a hash map (O(n) time, O(n) space); the canonical answer is Boyer-Moore voting — keep one candidate and a counter, cancel out non-matches, and the survivor is the majority in O(n) time and O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can go past the obvious hash-map count to the O(1)-space Boyer-Moore voting algorithm, and articulate WHY the cancellation invariant guarantees the survivor is the majority.
Where candidates slip
Resetting the candidate on every mismatch instead of only when count hits 0, or assuming Boyer-Moore works without a majority guarantee (it can return a wrong element if none exists).
How to stand out
State the hash-map baseline, then derive Boyer-Moore from the 'pair off opposite votes' image. Mention the divide-and-conquer O(n log n) middle ground and the > n/3 generalisation.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFind element appearing more than n/2 timesSpace budget?O(n) okO(1) requiredExplore the full treeCollapse the tree
nums = [2,2,1,1,1,2,2]How to read it:candidate and count evolve as we scan. count==0 triggers adopting a new candidate; the majority survives all cancellations.
- Frame 1
i=0, x=2count 0 → candidate=2, count=1
i↓2[0]2[1]1[2]1[3]1[4]2[5]2[6] - Frame 2
i=2, x=11 != 2 → count 2→1
2[0]2[1]i↓1[2]1[3]1[4]2[5]2[6] - Frame 3
i=4, x=11 != 2 → count 0; candidate still 2 but vulnerable
2[0]2[1]1[2]1[3]i↓1[4]2[5]2[6] - Frame 4
i=5, x=2count was 0 → candidate=2, count=1 (re-anchored)
2[0]2[1]1[2]1[3]1[4]i↓2[5]2[6] - Frame 5
donecandidate = 2 survives → return 2
2[0]2[1]1[2]1[3]1[4]2[5]i↓2[6]
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Hash Map Frequency Count (Naive)
1Hint 1Explore hintHide hint
The definition is literally about counts: which value appears more than n/2 times? What structure tracks 'how many times have I seen each value'?
2Hint 2Explore hintHide hint
Walk the array, incrementing a count per value in a hash map.
3Hint 3Explore hintHide hint
Either check after each increment whether the count crossed n/2, or do a second pass over the map to find the max. Return that value.
A · Core idea
Translate the definition directly: count how often each value appears, then return the one whose count exceeds ⌊n/2⌋. A hash map from value to running count does exactly this in one pass; you can return early the instant a count crosses the threshold.
Why this is the natural first attempt. The problem is phrased in terms of frequencies — "appears more than n/2 times" — so the most faithful translation is to actually tally frequencies. A hash map answers "how many of value x have I seen?" in O(1) average, so the whole thing is one linear scan with a counter per key. It's impossible to get wrong, which makes it a great baseline to state out loud.
Why the early return is safe. Because a majority is guaranteed, the moment any value's count exceeds n/2 you've found it — no other value can also exceed n/2 (two values each over half would total more than n elements). So you can bail out as soon as a counter crosses the line, often before finishing the scan.
Why it leaves something on the table. It spends O(n) memory to remember counts you mostly don't care about — you only need one value at the end. Interviewers pose Majority Element specifically to see whether you can collapse that bookkeeping into a single counter. The hash map is the answer that works; it's not the answer that impresses.
Why it still matters. It's the correctness anchor. When you later claim Boyer-Moore returns the majority, you can sanity-check against the intuition the hash map makes obvious: the majority is simply the value with the biggest tally, and Boyer-Moore is a clever way to find that value without storing all the tallies.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2,2,1,1,1,2,2]i=0..1
count 2 twice
{2: 2}2C · Code with teaching comments
Reference implementation previewpublic int majorityElement(int[] nums) { Map<Integer, Integer> counts = new HashMap<>(); int n = nums.length; for (int x : nums) { int c = counts.merge(x, 1, Integer::sum);Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Counting is the literal reading of the problem, and it exposes the key fact: only one value can exceed n/2. That uniqueness is exactly what Boyer-Moore exploits to avoid storing every count.
ComplexityO(n) time, O(n) space — One pass to build the map plus O(1) average increments → O(n) time. The map can hold up to n distinct keys → O(n) space.
E · Edge cases and pitfalls5nums = [1] — count of 1 becomes 1 > 0 → returns 1 immediately.Explore edge casesHide edge cases
Edge cases handled
nums = [1]count of 1 becomes 1 > 0 → returns 1 immediately.nums = [5,5,5,5]Crosses threshold at the third 5 (3 > 2) and returns early.
Pitfalls
- Using O(n) space when the problem expects O(1) — fine as a baseline only.
- Comparing with >= n/2 instead of > n/2 — the majority is strictly more than half.
- Forgetting integer division semantics of n/2 (it's ⌊n/2⌋).
Approach 2 of 2 · Optimal
Boyer-Moore Voting (Optimal)
1Hint 1Explore hintHide hint
You only ever need one value at the end. Could you get away with remembering just a single candidate and a counter, instead of every count?
2Hint 2Explore hintHide hint
Keep candidate and count. On each element: if count is 0, set candidate to this element. Then count++ if it matches the candidate, else count--.
3Hint 3Explore hintHide hint
Think of count as 'how many unmatched votes the current candidate has'. A mismatch cancels one vote. Because the majority has more votes than everyone else combined, it can never be cancelled to extinction — the final candidate is the answer.
A · Core idea
Sweep the array maintaining a single candidate and an integer count of its currently unmatched votes. When count is 0, the candidate slot is empty, so adopt the current element. Then add one vote if the element equals the candidate, or cancel one vote if it doesn't. The candidate left standing at the end is the majority.
The cancellation image. Imagine every element is a person voting for itself, and we repeatedly pair up two people who voted differently and send both home — their votes cancel. After all possible cancellations, whoever remains in the room is the survivor. Now here's the invariant: the majority element has strictly more than n/2 votes, which is strictly more than all other elements combined (they total fewer than n/2). Each cancellation removes one majority vote and one non-majority vote at most, so the non-majority side runs out of votes first. The majority can never be reduced to zero, so it must be the survivor. count is exactly the size of the 'unpaired' group for the current candidate.
Why we only re-anchor when `count == 0`. count measures how many votes the current candidate still has after cancellations. While count > 0, the candidate is still 'winning' the local tug-of-war, so a mismatch just trims its lead (count--). Only when count reaches 0 is the candidate fully cancelled and the slot genuinely empty — that's the one moment it's safe to switch to a new candidate. Switching on every mismatch instead (a common bug) throws away the running tally and breaks the invariant.
Why no verification pass is needed here. Boyer-Moore in general only produces a candidate — if no true majority exists, the survivor can be an arbitrary element, so you'd normally add a second pass to count it and confirm > n/2. This problem guarantees a majority exists, and a guaranteed majority is always the survivor, so we can return candidate directly. (Mention the verification pass anyway — it shows you understand the algorithm's limits.)
Why this is strictly better than the hash map. Same O(n) time, but the entire memory footprint is two integers regardless of how many distinct values appear. It's also a one-pass streaming algorithm: you could run it over a data stream you can't store. That space win is the reason interviewers prize this solution.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2,2,1,1,1,2,2]Array state
build lead
two 2s → cand=2, count=2
2C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Boyer-Moore is the realisation that you don't need every count to find the most frequent value when it's a strict majority — you only need to track whether it's still 'ahead' after pairing off opponents. The invariant 'a strict majority can't be fully cancelled' is the load-bearing idea, and it extends: for > n/3 you track two candidates, for > n/k you track k−1.
ComplexityO(n) time, O(1) space — A single pass with O(1) work per element → O(n) time. Only two scalar variables (candidate, count) are stored → O(1) space.
E · Edge cases and pitfalls7nums = [1] — count 0 → candidate=1, count=1; loop ends → return 1.Explore edge casesHide edge cases
Edge cases handled
nums = [1]count 0 → candidate=1, count=1; loop ends → return 1.nums = [1,2,1]cand=1,count=1; x=2 → count=0; x=1 → cand=1,count=1 → return 1.nums = [6,6,6,7,7]6 builds count to 3, two 7s drop it to 1, candidate stays 6 → return 6.
Pitfalls
- Re-assigning candidate on every mismatch instead of only when count == 0 — breaks the invariant.
- Returning candidate when no majority is guaranteed — needs a verification pass first.
- Initialising count to a nonzero value, so the first element is never adopted as candidate.
- Trying to extend this directly to > n/3 with one candidate — that needs two candidates.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int majorityElement(int[] nums) { int candidate = 0; int count = 0; for (int x : nums) { if (count == 0) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Re-anchoring on every mismatch
Switching candidate whenever the current element differs (rather than only when count is 0) discards the accumulated lead and can latch onto a minority element.
Explore the code comparisonHide the code comparison
Re-anchoring on every mismatch
Switching candidate whenever the current element differs (rather than only when count is 0) discards the accumulated lead and can latch onto a minority element.
Don't write this
for (int x : nums) {
if (x != candidate) {
candidate = x; // wrong: resets on every mismatch
count = 1;
} else {
count++;
}
}Write this instead
for (int x : nums) {
if (count == 0) {
candidate = x;
}
count += (x == candidate) ? 1 : -1;
}2Returning the candidate with no majority guarantee
Without a guaranteed majority, Boyer-Moore yields only a candidate. On nums = [1,2,3] it returns some element that isn't a majority. A verification pass is mandatory when existence isn't promised.
Explore the code comparisonHide the code comparison
Returning the candidate with no majority guarantee
Without a guaranteed majority, Boyer-Moore yields only a candidate. On nums = [1,2,3] it returns some element that isn't a majority. A verification pass is mandatory when existence isn't promised.
Don't write this
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate # unverifiedWrite this instead
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
if nums.count(candidate) > len(nums) // 2:
return candidate
return -1 # no majority3Strict vs non-strict majority threshold
The majority must appear MORE than ⌊n/2⌋ times. Using >= can wrongly accept a value that ties at exactly half (only possible to misjudge in the hash-map verification variant).
Explore the code comparisonHide the code comparison
Strict vs non-strict majority threshold
The majority must appear MORE than ⌊n/2⌋ times. Using >= can wrongly accept a value that ties at exactly half (only possible to misjudge in the hash-map verification variant).
Don't write this
if counts[x] >= n // 2:
return xWrite this instead
if counts[x] > n // 2:
return xRevise
Carry the pattern into the interview
Pattern to remember
Boyer-Moore majority voting
Code pattern to memorize
candidate = None, count = 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidateRules to remember
- 1Maintain one
candidateand onecount— that's the entireO(1)state. - 2When
counthits 0, adopt the current element as the new candidate. - 3Increment
counton a match, decrement on a mismatch — each mismatch cancels one candidate vote. - 4The majority element survives because it has more votes than everything else combined.
- 5No final verification needed when a majority is guaranteed to exist (it is, per the prompt).
- 6Boyer-Moore finds the >n/2 element only — for >n/3 you need two candidates.
Use this pattern when
- An element is guaranteed to appear **more than half** the time
- You need `O(1)` space — can't afford a frequency map
- Single pass / streaming is acceptable
- Counting 'is there a strict majority?' over a sequence
Choose another pattern when
- Need the element appearing > n/3 (or > n/k) → extended Boyer-Moore with k−1 candidates
- No guarantee a majority exists → you must add a verification pass
- Need full frequency distribution → use a hash map
- Array is sorted → the middle element nums[n/2] is the answer in O(1)
Interview takeaway
Boyer-Moore voting trades the hash map's O(n) space for a single counter by pairing off and cancelling opposing votes. The invariant — a true majority can never be fully cancelled because it outnumbers all others combined — is the reusable insight, and it generalises to the > n/3 and > n/k variants.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Boyer-Moore majority voting. Recognise it whenever a strict majority (> n/2) is guaranteed and O(1) space matters. The cancellation invariant — a strict majority can't be fully cancelled — generalises to > n/3 (two candidates) and > n/k (k−1 candidates). Hash-map counting is the obvious O(n)-space cousin.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Majority Element IIComing soonFind all elements appearing > n/3 times — extended Boyer-Moore with two candidates and counters.
- Check If a Number Is Majority Element in a Sorted ArrayComing soonBinary search the first and last occurrence; majority iff last - first + 1 > n/2.
- Online Majority Element In SubarrayComing soonAnswer majority queries on subarrays — random sampling plus binary search on occurrence indices.