Majority Element (LeetCode 169)
You will see how pairing off different values leaves the majority standing, in one pass with two variables.
In an integer array nums of length n, one value takes up more than half of the positions: it occurs more than ⌊n / 2⌋ times, and every input is built so that such a value exists. That value is called the majority element. Return it.
Follow-up: can you find it in linear time with only O(1) extra space?
Worked Examples
nums = [3,2,3]3nums = [2,2,1,1,1,2,2]2⚖️Formal Constraints & Bounds
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109The input is generated such that a majority element will exist in the array.
Why It Works & Core Invariant
Cancel each value against a different one: a value that fills more than half the array has more copies than all the others together, so some of its copies are still standing when the values run out.
Real-World Scenario & Production Applications
A cluster of replicas votes on a value, and more than half of them are known to agree; a stream of events is known to be dominated by one source. Counting every value needs memory that grows with the number of distinct values. Pairing off disagreeing values needs two variables, whatever the input size, and still finds the value that holds more than half.
Step-by-Step Execution Trace Table
Example 2, nums = [2,2,1,1,1,2,2] (the debugger's first preset; the trap is the step where 1 becomes the candidate):
x | count == 0 before x? | candidate | count after | What happened |
|---|---|---|---|---|
| 2 | yes | 2 | 1 | 2 starts a run |
| 2 | no | 2 | 2 | a second copy of 2 |
| 1 | no | 2 | 1 | 1 cancels one 2 |
| 1 | no | 2 | 0 | 1 cancels the other 2: the first four values are paired off |
| 1 | yes | 1 | 1 | 1 becomes the candidate, but 1 is not the majority: a candidate is only a survivor so far |
| 2 | no | 1 | 0 | 2 cancels the 1 |
| 2 | yes | 2 | 1 | 2 starts the last run |
| end | return candidate gives 2 |
| 1 | A value that fills more than half of `nums` has more copies than all the other values together: if each value cancels one copy of a different value, the majority still has copies left. |
| 2 | Keep this true: before each `x`, the values read so far, except `count` copies of `candidate`, split into pairs of different values. When `count == 0`, everything so far is paired off. |
| 3 | The shape: one loop over `nums` with two steps per value: first decide whether a new run starts, then update `count`. After the loop, return the value that is left standing. |
| 4 | The trap: the survivor is only a candidate. Here it is safe to return because a majority is promised; in the middle of `[2,2,1,1,1,2,2]` the candidate is `1`, and without the promise you must count it again. |
Target: Majority Element (LeetCode 169). Nothing is read yet, so nothing is standing; `count == 0` makes the first value the candidate.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting every value works, but it needs memory for every distinct value. Boyer-Moore Voting needs two variables. Picture each value cancelling one copy of a different value: two different values leave together. The majority fills more than half of nums, so even if every other value cancels one of its copies, some copies are left. The code keeps only what hasn't been cancelled yet: candidate and count, the number of its copies still unpaired. A matching x adds a copy, a different x cancels one, and when count reaches 0 the next x becomes the new candidate.
🗳️ The Analogy: A Shouting Match in a Room
People from several parties walk into a room one at a time. Whenever someone meets a supporter of a different party already standing there, the two of them leave together. Supporters of the same party stay and wait. If one party brought more than half of all the people, the others can't pair off all of them: when the door closes, the people still standing belong to that party. You only ever need to remember which party is standing and how many of its people are there.
🪄 The Mathematical Harmony / Magic Trick
if count == 0: candidate = xcount += 1 if x == candidate else -1return candidate Before each x, the values already read, except count copies of candidate, can be split into pairs of different values. Each pair holds at most one copy of the majority, and there are fewer other values than copies of the majority, so the pairs can't use up all of its copies: it must be the value left standing at the end. The trap: that is a promise about the end only, and only because a majority exists. In the middle of [2,2,1,1,1,2,2] the candidate is 1, and on [1, 2, 3] the survivor is 3, which occurs once; when a majority is not promised, count the survivor again.
💡 Summary
One pass: when count == 0 take x as candidate, then count += 1 if x == candidate else -1; return candidate. Two variables: time, space.
Trusting the survivor without a promise (the trap):
return candidateis right here only because a majority exists. In the middle of[2,2,1,1,1,2,2]the candidate is1, and on[1, 2, 3]the survivor is3, which occurs once; when no majority is promised, count the candidate again in a second pass.Switching candidates at the wrong moment: test
count == 0before countingx, then countxfor its new run. Counting first and thenif count == 0: candidate = xhands the lead to the value that just cancelled the last copy, with no copy of its own, and[3, 1, 3]returns1.Skipping the last value: a loop over
nums[:-1]never counts it, and[1, 2, 2]returns1.Returning the early leader: the candidate with the largest
countso far is not the answer; the lead changes, and only the value standing at the end counts.Counting every value: a hash map of counts is correct and
O(N)time, but it usesO(N)extra space; the follow-up asks forO(1), which is what the pairing-off gives.
4-Phase Thought Process Model
You will see how a senior engineer spots a more-than-half guarantee and defends pairing off values out loud.
Pattern Recognition Signals
The 10-second spot
One value takes up "more than half of the positions", "every input is built so that such a value exists", and the follow-up asks for "only O(1) extra space": no count per value is allowed, and a value that holds more than half can't be cancelled out by all the others together. That is Boyer-Moore Voting.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before each x, the values read so far, except count copies of candidate, split into pairs of different values. if count == 0: candidate = x, then count += 1 if x == candidate else -1; at the end, candidate is the majority.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
return candidateis only safe because the input promises a majority: on[1, 2, 3]the survivor is3, which occurs once, and in the middle of[2,2,1,1,1,2,2]the candidate is1. Without the promise, as in Majority Element II (LC 229), count the survivor again.Test
count == 0before countingx, and letxcount for itself: counting first and thenif count == 0: candidate = xhands the lead to the value that just cancelled the last copy, with no copy of its own, and[3, 1, 3]returns1.Read every value: a loop over
nums[:-1]misses the last one, and[1, 2, 2]returns1.Don't return the candidate that led with the largest
count: the lead changes, and only the value standing at the end is the answer.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Boyer-Moore Voting. The majority fills more than half the array, so if every value cancels one copy of a different value, the majority still has copies left over. I keep two variables: a candidate and a count of its copies that haven't been cancelled yet. For each value, if the count is zero, that value becomes the candidate; then a match adds one to the count and a different value subtracts one. Each subtraction removes two different values, at most one of them the majority, so the majority can't be paired off completely, and it's the candidate at the end. The trap is trusting the candidate too early or without a guarantee: in the middle of the example the candidate is the wrong value, and on an array with no majority the survivor means nothing, so there I'd count it in a second pass. One pass,
O(N)time,O(1)space.
So: cancel different values in pairs, take a new candidate only at count == 0, and trust the survivor only because a majority is promised.
Complexity & Mathematical Proof
O(N)
Look at the code: for x in nums runs N times, and each round does one comparison count == 0, at most one assignment candidate = x, one comparison x == candidate and one addition. That is O(1) per value, so the pass is O(N). There is no second pass, because the input promises a majority.
O(1)
candidate and count are two variables whatever N is: O(1) extra space. The answer is one integer.
T(N) = N · O(1) = O(N)
Look at the code: for x in nums runs N times, and each round does one comparison count == 0, at most one assignment candidate = x, one comparison x == candidate and one addition. That is O(1) per value, so the pass is O(N). There is no second pass, because the input promises a majority.
Derivation Progression
O(1)
candidate, count = None, 0.
N · O(1)
for x in nums: one count == 0 test, at most one assignment, one x == candidate test and one addition per value.
O(N)
One pass, constant work per value, no verification pass (a majority is promised).
Variable Definitions
Number of values, len(nums) (at most 5 * 104)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): candidate and count
O(1): one integer
Boundary Best / Worst Cases
: every value is read once
: the same single pass
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "more than half of the positions", "only ``O(1)`` extra space". A value that holds more than half of the input, found without a count per value: Boyer-Moore Voting, pairing off different values.
values in . A hash map of counts is time but memory, and sorting is ; voting is one pass with two variables: time, space.
The survivor is only a candidate: here a majority is promised, but on data without that promise it must be counted again, which needs a second pass over the data (or a replay of the stream). Two partial results merge: the same candidate adds its counts; different candidates keep the one with the larger count, with the difference as its count, so shards can vote on their own and combine.
Core Algorithmic State Invariants
`count += 1 if x == candidate else -1`: a different value cancels one unpaired copy of `candidate`, so two different values leave together, and at most one of them is the majority.
A value that fills more than half of `nums` has more copies than all the other values together, so it is the `candidate` still standing at the end, but only because a majority is promised.
`candidate` and `count` are all the state: one pass over `nums` with O(1) work per value, O(N) time and O(1) extra space.
Majority Element (LeetCode 169)
You will see how pairing off different values leaves the majority standing, in one pass with two variables.
In an integer array nums of length n, one value takes up more than half of the positions: it occurs more than ⌊n / 2⌋ times, and every input is built so that such a value exists. That value is called the majority element. Return it.
Follow-up: can you find it in linear time with only O(1) extra space?
Worked Examples
nums = [3,2,3]3nums = [2,2,1,1,1,2,2]2⚖️Formal Constraints & Bounds
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109The input is generated such that a majority element will exist in the array.
Why It Works & Core Invariant
Cancel each value against a different one: a value that fills more than half the array has more copies than all the others together, so some of its copies are still standing when the values run out.
Real-World Scenario & Production Applications
A cluster of replicas votes on a value, and more than half of them are known to agree; a stream of events is known to be dominated by one source. Counting every value needs memory that grows with the number of distinct values. Pairing off disagreeing values needs two variables, whatever the input size, and still finds the value that holds more than half.
Step-by-Step Execution Trace Table
Example 2, nums = [2,2,1,1,1,2,2] (the debugger's first preset; the trap is the step where 1 becomes the candidate):
x | count == 0 before x? | candidate | count after | What happened |
|---|---|---|---|---|
| 2 | yes | 2 | 1 | 2 starts a run |
| 2 | no | 2 | 2 | a second copy of 2 |
| 1 | no | 2 | 1 | 1 cancels one 2 |
| 1 | no | 2 | 0 | 1 cancels the other 2: the first four values are paired off |
| 1 | yes | 1 | 1 | 1 becomes the candidate, but 1 is not the majority: a candidate is only a survivor so far |
| 2 | no | 1 | 0 | 2 cancels the 1 |
| 2 | yes | 2 | 1 | 2 starts the last run |
| end | return candidate gives 2 |
| 1 | A value that fills more than half of `nums` has more copies than all the other values together: if each value cancels one copy of a different value, the majority still has copies left. |
| 2 | Keep this true: before each `x`, the values read so far, except `count` copies of `candidate`, split into pairs of different values. When `count == 0`, everything so far is paired off. |
| 3 | The shape: one loop over `nums` with two steps per value: first decide whether a new run starts, then update `count`. After the loop, return the value that is left standing. |
| 4 | The trap: the survivor is only a candidate. Here it is safe to return because a majority is promised; in the middle of `[2,2,1,1,1,2,2]` the candidate is `1`, and without the promise you must count it again. |
Target: Majority Element (LeetCode 169). Nothing is read yet, so nothing is standing; `count == 0` makes the first value the candidate.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting every value works, but it needs memory for every distinct value. Boyer-Moore Voting needs two variables. Picture each value cancelling one copy of a different value: two different values leave together. The majority fills more than half of nums, so even if every other value cancels one of its copies, some copies are left. The code keeps only what hasn't been cancelled yet: candidate and count, the number of its copies still unpaired. A matching x adds a copy, a different x cancels one, and when count reaches 0 the next x becomes the new candidate.
🗳️ The Analogy: A Shouting Match in a Room
People from several parties walk into a room one at a time. Whenever someone meets a supporter of a different party already standing there, the two of them leave together. Supporters of the same party stay and wait. If one party brought more than half of all the people, the others can't pair off all of them: when the door closes, the people still standing belong to that party. You only ever need to remember which party is standing and how many of its people are there.
🪄 The Mathematical Harmony / Magic Trick
if count == 0: candidate = xcount += 1 if x == candidate else -1return candidate Before each x, the values already read, except count copies of candidate, can be split into pairs of different values. Each pair holds at most one copy of the majority, and there are fewer other values than copies of the majority, so the pairs can't use up all of its copies: it must be the value left standing at the end. The trap: that is a promise about the end only, and only because a majority exists. In the middle of [2,2,1,1,1,2,2] the candidate is 1, and on [1, 2, 3] the survivor is 3, which occurs once; when a majority is not promised, count the survivor again.
💡 Summary
One pass: when count == 0 take x as candidate, then count += 1 if x == candidate else -1; return candidate. Two variables: time, space.
Trusting the survivor without a promise (the trap):
return candidateis right here only because a majority exists. In the middle of[2,2,1,1,1,2,2]the candidate is1, and on[1, 2, 3]the survivor is3, which occurs once; when no majority is promised, count the candidate again in a second pass.Switching candidates at the wrong moment: test
count == 0before countingx, then countxfor its new run. Counting first and thenif count == 0: candidate = xhands the lead to the value that just cancelled the last copy, with no copy of its own, and[3, 1, 3]returns1.Skipping the last value: a loop over
nums[:-1]never counts it, and[1, 2, 2]returns1.Returning the early leader: the candidate with the largest
countso far is not the answer; the lead changes, and only the value standing at the end counts.Counting every value: a hash map of counts is correct and
O(N)time, but it usesO(N)extra space; the follow-up asks forO(1), which is what the pairing-off gives.
4-Phase Thought Process Model
You will see how a senior engineer spots a more-than-half guarantee and defends pairing off values out loud.
Pattern Recognition Signals
The 10-second spot
One value takes up "more than half of the positions", "every input is built so that such a value exists", and the follow-up asks for "only O(1) extra space": no count per value is allowed, and a value that holds more than half can't be cancelled out by all the others together. That is Boyer-Moore Voting.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before each x, the values read so far, except count copies of candidate, split into pairs of different values. if count == 0: candidate = x, then count += 1 if x == candidate else -1; at the end, candidate is the majority.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
return candidateis only safe because the input promises a majority: on[1, 2, 3]the survivor is3, which occurs once, and in the middle of[2,2,1,1,1,2,2]the candidate is1. Without the promise, as in Majority Element II (LC 229), count the survivor again.Test
count == 0before countingx, and letxcount for itself: counting first and thenif count == 0: candidate = xhands the lead to the value that just cancelled the last copy, with no copy of its own, and[3, 1, 3]returns1.Read every value: a loop over
nums[:-1]misses the last one, and[1, 2, 2]returns1.Don't return the candidate that led with the largest
count: the lead changes, and only the value standing at the end is the answer.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Boyer-Moore Voting. The majority fills more than half the array, so if every value cancels one copy of a different value, the majority still has copies left over. I keep two variables: a candidate and a count of its copies that haven't been cancelled yet. For each value, if the count is zero, that value becomes the candidate; then a match adds one to the count and a different value subtracts one. Each subtraction removes two different values, at most one of them the majority, so the majority can't be paired off completely, and it's the candidate at the end. The trap is trusting the candidate too early or without a guarantee: in the middle of the example the candidate is the wrong value, and on an array with no majority the survivor means nothing, so there I'd count it in a second pass. One pass,
O(N)time,O(1)space.
So: cancel different values in pairs, take a new candidate only at count == 0, and trust the survivor only because a majority is promised.
Complexity & Mathematical Proof
O(N)
Look at the code: for x in nums runs N times, and each round does one comparison count == 0, at most one assignment candidate = x, one comparison x == candidate and one addition. That is O(1) per value, so the pass is O(N). There is no second pass, because the input promises a majority.
O(1)
candidate and count are two variables whatever N is: O(1) extra space. The answer is one integer.
T(N) = N · O(1) = O(N)
Look at the code: for x in nums runs N times, and each round does one comparison count == 0, at most one assignment candidate = x, one comparison x == candidate and one addition. That is O(1) per value, so the pass is O(N). There is no second pass, because the input promises a majority.
Derivation Progression
O(1)
candidate, count = None, 0.
N · O(1)
for x in nums: one count == 0 test, at most one assignment, one x == candidate test and one addition per value.
O(N)
One pass, constant work per value, no verification pass (a majority is promised).
Variable Definitions
Number of values, len(nums) (at most 5 * 104)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): candidate and count
O(1): one integer
Boundary Best / Worst Cases
: every value is read once
: the same single pass
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "more than half of the positions", "only ``O(1)`` extra space". A value that holds more than half of the input, found without a count per value: Boyer-Moore Voting, pairing off different values.
values in . A hash map of counts is time but memory, and sorting is ; voting is one pass with two variables: time, space.
The survivor is only a candidate: here a majority is promised, but on data without that promise it must be counted again, which needs a second pass over the data (or a replay of the stream). Two partial results merge: the same candidate adds its counts; different candidates keep the one with the larger count, with the difference as its count, so shards can vote on their own and combine.
Core Algorithmic State Invariants
`count += 1 if x == candidate else -1`: a different value cancels one unpaired copy of `candidate`, so two different values leave together, and at most one of them is the majority.
A value that fills more than half of `nums` has more copies than all the other values together, so it is the `candidate` still standing at the end, but only because a majority is promised.
`candidate` and `count` are all the state: one pass over `nums` with O(1) work per value, O(N) time and O(1) extra space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| The survivor so far and its unpaired copies | candidate, count = None, 0 | Nothing is read yet, so nothing is standing; `count == 0` makes the first value the candidate. |
| Read every value once | for x in nums: | One pass, in any order: the pairing argument doesn't care where the copies are. |
| Everything before is paired off: start a new run | if count == 0:
candidate = x | Checked before `x` is counted, so `x` counts for itself and `count` never goes below 0. |
| A match adds a copy, a different value cancels one | count += 1 if x == candidate else -1 | A cancellation removes two different values, at most one of them the majority. |
| The value left standing | return candidate | Safe here only because a majority is promised; otherwise count it again. |