Majority Element (LeetCode 169)
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]3n = 3, so the majority needs more than 1 copy. 3 occurs twice.nums = [2,2,1,1,1,2,2]2n = 7, so the majority needs more than 3 copies. 2 occurs four times and 1 three times.⚖️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.
Core Insight
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 |
The Math, Step by Step
1. The counts the code relies on
Let be the length of nums, and let be the majority value. The problem guarantees that occurs more than times. So occurs more often than all other values together:
The code keeps two variables. candidate is a value, and count is the number of copies of candidate that are not yet cancelled.
2. One step: an element either adds a copy or cancels one
For each element x, one of three things happens:
| Case | What the code does | Meaning |
|---|---|---|
count == 0 | candidate = x, then count becomes 1 | nothing is left over, so x starts a new candidate |
x == candidate | count += 1 | one more uncancelled copy of the candidate |
x != candidate | count -= 1 | x and one copy of the candidate cancel each other |
Each cancellation removes a pair of two different values: x and one earlier copy of the candidate. After any prefix of nums, the elements seen so far split into cancelled pairs of different values, plus count copies of candidate that are left over.
3. Why the majority is the candidate at the end
Every cancelled pair holds two different values, so it holds at most one copy of . So each copy of inside a pair uses up one element that is not . The elements that are not number fewer than the copies of . So the pairs cannot use up every copy of . At least one copy of is left over at the end.
The left-over elements are all copies of candidate. At least one of them is , so candidate is , and count is at least 1. This argument is the Boyer-Moore voting algorithm.
The argument needs the guarantee of part 1. Without a majority, the final candidate can be any value. For example, [1, 2, 3] ends with candidate 3, which is not a majority. The problem promises a majority, so the code does not check it.
4. When count is 0
count == 0 means every element seen so far is inside a cancelled pair. The next element starts a new candidate. The order inside the loop matters. The code first sets candidate = x and then runs count += 1 if x == candidate else -1. Because x now equals candidate, count becomes 1. So count never drops below 0.
A candidate can change many times, as in Example 2. The only thing that matters is the candidate after the last element.
5. Example 2 by hand
nums = [2,2,1,1,1,2,2], so . The value 2 occurs 4 times, more than .
x | count == 0 before? | candidate | count after | What happened |
|---|---|---|---|---|
| 2 | yes | 2 | 1 | new candidate 2 |
| 2 | no | 2 | 2 | one more 2 |
| 1 | no | 2 | 1 | this 1 cancels one 2 |
| 1 | no | 2 | 0 | this 1 cancels the other 2 |
| 1 | yes | 1 | 1 | new candidate 1 |
| 2 | no | 1 | 0 | this 2 cancels the 1 |
| 2 | yes | 2 | 1 | new candidate 2 |
The cancelled pairs are (2, 1), (2, 1) and (1, 2). Each holds one 2 and one 1. The left-over element is the last 2. The code returns 2, the expected output.
6. Example 1 by hand
nums = [3,2,3]. The first 3 becomes the candidate with count = 1. The 2 cancels it, so count is 0. The last 3 starts a new candidate with count = 1. The code returns 3, the expected output.
7. From the math to the code
| Math | In majorityElement |
|---|---|
| nothing seen, nothing left over | candidate, count = None, 0 |
| everything so far is cancelled | if count == 0: followed by candidate = x |
| one more left-over copy | count += 1 when x == candidate |
| a pair of different values cancels | count -= 1 when x != candidate |
| the left-over value is the majority | return candidate |
The loop reads each element once, so the code takes time. It keeps two variables, so it uses extra space.
| 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. |
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.
🔑 Why It Works
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.
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 comparesxwith the oldcandidate. Withcandidate, count = None, 0, the first value subtracts 1, socountbecomes -1 and never returns to 0. Then[3, 1, 3]returnsNone.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
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
Decision rule: if count == 0: candidate = x, then count += 1 if x == candidate else -1; return candidate after the last x.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Reading
countas how oftencandidateoccurs: it counts only the copies not paired off, so on[2,2,1,1,1,2,2]it ends at1, not4.
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.
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)
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
Pointer Invariant Transition Progression
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.
When shards merge, different candidates must cancel (larger count minus smaller), never add: adding would let a value that is not the majority collect votes it never had. On a stream, keep the data replayable if the majority is not guaranteed, because the check needs a second look.
Majority Element (LeetCode 169)
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]3n = 3, so the majority needs more than 1 copy. 3 occurs twice.nums = [2,2,1,1,1,2,2]2n = 7, so the majority needs more than 3 copies. 2 occurs four times and 1 three times.⚖️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.
Core Insight
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 |
The Math, Step by Step
1. The counts the code relies on
Let be the length of nums, and let be the majority value. The problem guarantees that occurs more than times. So occurs more often than all other values together:
The code keeps two variables. candidate is a value, and count is the number of copies of candidate that are not yet cancelled.
2. One step: an element either adds a copy or cancels one
For each element x, one of three things happens:
| Case | What the code does | Meaning |
|---|---|---|
count == 0 | candidate = x, then count becomes 1 | nothing is left over, so x starts a new candidate |
x == candidate | count += 1 | one more uncancelled copy of the candidate |
x != candidate | count -= 1 | x and one copy of the candidate cancel each other |
Each cancellation removes a pair of two different values: x and one earlier copy of the candidate. After any prefix of nums, the elements seen so far split into cancelled pairs of different values, plus count copies of candidate that are left over.
3. Why the majority is the candidate at the end
Every cancelled pair holds two different values, so it holds at most one copy of . So each copy of inside a pair uses up one element that is not . The elements that are not number fewer than the copies of . So the pairs cannot use up every copy of . At least one copy of is left over at the end.
The left-over elements are all copies of candidate. At least one of them is , so candidate is , and count is at least 1. This argument is the Boyer-Moore voting algorithm.
The argument needs the guarantee of part 1. Without a majority, the final candidate can be any value. For example, [1, 2, 3] ends with candidate 3, which is not a majority. The problem promises a majority, so the code does not check it.
4. When count is 0
count == 0 means every element seen so far is inside a cancelled pair. The next element starts a new candidate. The order inside the loop matters. The code first sets candidate = x and then runs count += 1 if x == candidate else -1. Because x now equals candidate, count becomes 1. So count never drops below 0.
A candidate can change many times, as in Example 2. The only thing that matters is the candidate after the last element.
5. Example 2 by hand
nums = [2,2,1,1,1,2,2], so . The value 2 occurs 4 times, more than .
x | count == 0 before? | candidate | count after | What happened |
|---|---|---|---|---|
| 2 | yes | 2 | 1 | new candidate 2 |
| 2 | no | 2 | 2 | one more 2 |
| 1 | no | 2 | 1 | this 1 cancels one 2 |
| 1 | no | 2 | 0 | this 1 cancels the other 2 |
| 1 | yes | 1 | 1 | new candidate 1 |
| 2 | no | 1 | 0 | this 2 cancels the 1 |
| 2 | yes | 2 | 1 | new candidate 2 |
The cancelled pairs are (2, 1), (2, 1) and (1, 2). Each holds one 2 and one 1. The left-over element is the last 2. The code returns 2, the expected output.
6. Example 1 by hand
nums = [3,2,3]. The first 3 becomes the candidate with count = 1. The 2 cancels it, so count is 0. The last 3 starts a new candidate with count = 1. The code returns 3, the expected output.
7. From the math to the code
| Math | In majorityElement |
|---|---|
| nothing seen, nothing left over | candidate, count = None, 0 |
| everything so far is cancelled | if count == 0: followed by candidate = x |
| one more left-over copy | count += 1 when x == candidate |
| a pair of different values cancels | count -= 1 when x != candidate |
| the left-over value is the majority | return candidate |
The loop reads each element once, so the code takes time. It keeps two variables, so it uses extra space.
| 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. |
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.
🔑 Why It Works
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.
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 comparesxwith the oldcandidate. Withcandidate, count = None, 0, the first value subtracts 1, socountbecomes -1 and never returns to 0. Then[3, 1, 3]returnsNone.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
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
Decision rule: if count == 0: candidate = x, then count += 1 if x == candidate else -1; return candidate after the last x.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Reading
countas how oftencandidateoccurs: it counts only the copies not paired off, so on[2,2,1,1,1,2,2]it ends at1, not4.
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.
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)
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
Pointer Invariant Transition Progression
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.
When shards merge, different candidates must cancel (larger count minus smaller), never add: adding would let a value that is not the majority collect votes it never had. On a stream, keep the data replayable if the majority is not guaranteed, because the check needs a second look.