What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Two Pointers & Sliding Window

P3MediumMental model~4 min speedrun

Boyer-Moore Voting (Majority Element)

Majority Element (LC 169)(opens leetcode.com)

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?

Example 1

Input:nums = [3,2,3]

Output:3

n = 3, so the majority needs more than 1 copy. 3 occurs twice.

Boyer-Moore Voting

Spot it when: A value holds more than a fixed share of the input (more than half, or more than n / k for a small k), and you must find it in one pass with O(1) extra space, so no count per value.

Not this one if…

The array is sorted and the value to test is given, as in Check If a Number Is Majority Element in a Sorted Array (LC 1150): two binary searches find where its copies start and end, faster than any pass over the array. See Lower Bound

Boyer-Moore Voting

Python

1	def majority_element(nums: list[int]) -> int:
2	"""Majority Element: pair off different values; the majority is the value left standing.
3	Time: O(N) \| Space: O(1)
4	"""
5	# candidate, count: the value currently "standing" and how many of its copies are not yet
6	# paired off against a different value.
7	candidate, count = None, 0
8
9	# 1. Decide This Value's Role, Then Update The Tally:
10	# Everything read before a count of 0 is already paired off, so x starts a new run;
11	# counting after that check means x always counts as its own first copy, and count never
12	# goes below 0.
13	for x in nums:
14	if count == 0:
15	candidate = x
16	count += 1 if x == candidate else -1
17
18	# 2. Report The Value Left Standing:
19	# A value that fills more than half of nums has more copies than everything else combined,
20	# so pairing off different values can never cancel it; it is the one still standing at the end.
21	return candidate

Invariant: Before each x, the values read so far, except count copies of candidate, split into pairs of different values that cancel each other out.

Let every value cancel one copy of a different value: a value that fills more than half of nums has more copies than all the others together, so it can't be cancelled out, and the code only has to remember what is still standing, candidate and count. When count == 0 everything read so far is paired off, so x becomes the new candidate; then count += 1 if x == candidate else -1 either adds a copy or removes a pair of two different values, at most one of them the majority, which is why the majority is the candidate left at the end. The trap is trusting that survivor: it is the answer only when a majority is promised (in the middle of [2,2,1,1,1,2,2] the candidate is 1, and on [1, 2, 3] the survivor occurs once), so when the promise is missing, count the survivor again in a second pass.

See it run

Boyer-Moore Voting, step by step

candidate Nonecount 0

The top row is nums. The middle row is candidate after each value. The bottom row is count after each value.

x the value being read
candidate the value standing after this step
count its copies not yet paired off

Start: candidate is None and count is 0. nums has 7 values, and each one will add a copy or cancel one.

nums

candidate

count

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Returning candidate when no majority is promised
Mistake
```
return candidate
```
Fix
```
if nums.count(candidate) > len(nums) // 2:
    return candidate
return None
```
What happens: The last candidate is the majority only when a majority exists. Majority Element (LC 169) promises one, so the blueprint can return it. Without that promise, the survivor can be any value. Count it in a second pass before returning it.
Example: nums = [1, 2, 3], with no majority promised
Mistake: returns 3Fix: returns None
Gotcha 2: Looping over nums[:-1] and skipping the last value
Mistake
```
for x in nums[:-1]:
```
Fix
```
for x in nums:
```
What happens: Every value must cancel or add one copy. nums[:-1] leaves out the last value. When that value decides the result, the wrong candidate is left standing.
Example: nums = [1, 2, 2]
Mistake: returns 1Fix: returns 2
Gotcha 3: Counting x before testing count == 0
Mistake
```
count += 1 if x == candidate else -1
if count == 0:
    candidate = x
```
Fix
```
if count == 0:
    candidate = x
count += 1 if x == candidate else -1
```
What happens: When count is 0, every value read so far is paired off. The new value x must start the new run and count as its first copy. Counting first compares x with the old candidate. At the start, candidate is None, so the first value subtracts 1 and count becomes -1. count then never returns to 0, and candidate stays None.
Example: nums = [3, 1, 3]
Mistake: returns NoneFix: returns 3
Gotcha 4: Returning the value that led with the largest count
Mistake
```
if count > best_count:
    best, best_count = candidate, count
```
Fix
```
return candidate
```
What happens: The lead changes as the pairs cancel. A value can hold the largest count early and still be paired off later. Only the candidate standing after the last value is the majority.
Example: nums = [1, 1, 2, 2, 2]
Mistake: returns 1Fix: returns 2

Deep Dive

Cancel different values in pairs

A majority value appears more than n / 2 times. Take any two different values and remove them together. This removes at most one copy of the majority value and at least one copy of another value.

Repeat until no such pair is left. Every value that remains is the same value. The majority value had more copies than all other values together, so it still has copies after the removals. The value that remains is the majority value.

The code does not store the pairs. It stores only candidate, the value that is not yet paired off, and count, the number of its copies that are not yet paired off. That is O(1) space.

Majority Element, traced on seven values

Take nums = [2, 2, 1, 1, 1, 2, 2]. candidate is None and count is 0.

The first 2 finds count == 0, so candidate = 2 and count = 1. The second 2 gives count = 2. The first 1 differs from candidate, so one pair cancels and count = 1. The second 1 cancels again and count = 0.

The third 1 finds count == 0, so candidate = 1 and count = 1. Here the survivor is 1, which is not the answer. The next 2 cancels it and count = 0. The last 2 finds count == 0, so candidate = 2 and count = 1.

The survivor is 2, and 2 occurs 4 times in 7 values, so it is the majority value. The final count is 1, which is not the number of times 2 occurs. count is only the number of copies not yet paired off.

The board marks the trap before the last step. The survivor is the answer only because a majority is promised. For nums = [1, 2, 3] the survivor is 3, and it occurs once.

Why the order of the two lines matters

The loop first tests count == 0, then updates count. When count is 0, every value read so far is paired off, so x starts a new run and counts as its own first copy.

If the update runs first, x is compared with the old candidate. At the start candidate is None, so the first value subtracts 1 and count becomes -1. For nums = [3, 1, 3] the count never returns to 0, candidate stays None, and the code returns None instead of 3.

With the right order, count never goes below 0.

Cost, and more than n / k

The loop reads each value once and keeps two variables, so the time is O(N) and the space is O(1). A hash map of counts also takes O(N) time, but it needs O(N) space. Sorting needs O(N log N) time.

The same idea works for a share of n / k. At most k - 1 values can appear more than n / k times, so keep k - 1 candidates with a count each. A value that does not match any candidate cancels one copy of every candidate. Majority Element II (LC 229) uses k = 3 and two candidates.

That problem does not promise that the candidates are real. So a second pass counts each candidate and keeps only those with more than n // 3 copies. The same second pass is the safe version of Majority Element (LC 169) when no majority is promised.

60-Second Pitch

"A majority value has more copies than all other values together. If I remove two different values at a time, each removal takes at most one copy of the majority, so the majority is never cancelled out. I keep only the value not yet paired off. candidate is that value and count is how many of its copies are left. When count == 0, x becomes the new candidate. Then count goes up by 1 for a match and down by 1 for a different value. That is one pass, O(N) time and O(1) space. The survivor is the answer only when a majority is promised. Otherwise I count it in a second pass. For more than n / 3 I keep two candidates in the same way."

Common Questions

Why does the majority value always survive?: Each cancellation removes two different values, so it removes at most one copy of the majority value. The majority value has more copies than all other values together. After all cancellations, copies of the majority value are still left, and everything that is left is one value.
What if there may be no majority value?: The survivor can then be any value. Count it in a second pass and return it only when nums.count(candidate) > len(nums) // 2. Otherwise return None. The second pass is still O(N) time and O(1) space.
How do you find values that appear more than n / 3 times?: Keep two candidates, each with its own count. A new value that equals one candidate adds a copy to it. A new value that equals neither takes a free slot if one exists, otherwise it subtracts one from both counts. Then count each candidate in a second pass. See Majority Element II (LC 229).
What does the final count mean?: It is the number of copies of candidate not yet paired off. It is not the number of times the value occurs. On [2, 2, 1, 1, 1, 2, 2] the final count is 1, and 2 occurs 4 times.
Why not use a hash map or sort the array?: A hash map of counts takes O(N) time but O(N) space. Sorting takes O(N log N) time, and the middle element is the majority. Voting takes O(N) time and O(1) space, which is why it is the expected answer when the memory limit matters.

SWE Reasoning

Spot it

A value holds more than a fixed share of the input (more than half, or more than n / k for a small k), as in Majority Element (LC 169) and Majority Element II (LC 229).
The answer must come in one pass with O(1) extra space, so a count per value is not allowed.
A majority is promised, or a second pass can check the survivor.

The invariant, step by step

candidate is None and count is 0. Nothing has been read.
For each x, if count == 0, everything read so far is paired off, so candidate = x.
Then count += 1 if x == candidate else -1. A matching value adds one copy. A different value cancels one copy and removes a pair of two different values.
Before each x, the values read so far, except count copies of candidate, are split into pairs of different values.
A pair contains at most one copy of the majority value, so the majority value cannot be cancelled out. It is the candidate after the last value.

Traps

Trusting the survivor without a promise. On [1, 2, 3] the survivor 3 occurs once. Count it in a second pass unless a majority is promised.
Looping over nums[:-1]. The last value is never read. On [1, 2, 2] the code returns 1 instead of 2.
Counting x before testing count == 0. On [3, 1, 3] the first value gives count = -1, and candidate stays None.
Returning the value with the largest count seen. The lead changes as pairs cancel. On [1, 1, 2, 2, 2] it returns 1 instead of 2.

Practice

Canonical LeetCode:Majority Element (LC 169)Majority Element II (LC 229)Minimum Index of a Valid Split (LC 2780)

Theory Context•Two Pointers & Sliding Window

P3MediumMental model~4 min speedrun

Boyer-Moore Voting (Majority Element)

Majority Element (LC 169)(opens leetcode.com)

Follow-up: can you find it in linear time with only O(1) extra space?

Example 1

Input:nums = [3,2,3]

Output:3

n = 3, so the majority needs more than 1 copy. 3 occurs twice.

Boyer-Moore Voting

Not this one if…

The array is sorted and the value to test is given, as in Check If a Number Is Majority Element in a Sorted Array (LC 1150): two binary searches find where its copies start and end, faster than any pass over the array. See Lower Bound

Boyer-Moore Voting

Python

1	def majority_element(nums: list[int]) -> int:
2	"""Majority Element: pair off different values; the majority is the value left standing.
3	Time: O(N) \| Space: O(1)
4	"""
5	# candidate, count: the value currently "standing" and how many of its copies are not yet
6	# paired off against a different value.
7	candidate, count = None, 0
8
9	# 1. Decide This Value's Role, Then Update The Tally:
10	# Everything read before a count of 0 is already paired off, so x starts a new run;
11	# counting after that check means x always counts as its own first copy, and count never
12	# goes below 0.
13	for x in nums:
14	if count == 0:
15	candidate = x
16	count += 1 if x == candidate else -1
17
18	# 2. Report The Value Left Standing:
19	# A value that fills more than half of nums has more copies than everything else combined,
20	# so pairing off different values can never cancel it; it is the one still standing at the end.
21	return candidate

Invariant: Before each x, the values read so far, except count copies of candidate, split into pairs of different values that cancel each other out.

See it run

Boyer-Moore Voting, step by step

candidate Nonecount 0

The top row is nums. The middle row is candidate after each value. The bottom row is count after each value.

x the value being read
candidate the value standing after this step
count its copies not yet paired off

Start: candidate is None and count is 0. nums has 7 values, and each one will add a copy or cancel one.

nums

candidate

count

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Returning candidate when no majority is promised
Mistake
```
return candidate
```
Fix
```
if nums.count(candidate) > len(nums) // 2:
    return candidate
return None
```
What happens: The last candidate is the majority only when a majority exists. Majority Element (LC 169) promises one, so the blueprint can return it. Without that promise, the survivor can be any value. Count it in a second pass before returning it.
Example: nums = [1, 2, 3], with no majority promised
Mistake: returns 3Fix: returns None
Gotcha 2: Looping over nums[:-1] and skipping the last value
Mistake
```
for x in nums[:-1]:
```
Fix
```
for x in nums:
```
What happens: Every value must cancel or add one copy. nums[:-1] leaves out the last value. When that value decides the result, the wrong candidate is left standing.
Example: nums = [1, 2, 2]
Mistake: returns 1Fix: returns 2
Gotcha 3: Counting x before testing count == 0
Mistake
```
count += 1 if x == candidate else -1
if count == 0:
    candidate = x
```
Fix
```
if count == 0:
    candidate = x
count += 1 if x == candidate else -1
```
What happens: When count is 0, every value read so far is paired off. The new value x must start the new run and count as its first copy. Counting first compares x with the old candidate. At the start, candidate is None, so the first value subtracts 1 and count becomes -1. count then never returns to 0, and candidate stays None.
Example: nums = [3, 1, 3]
Mistake: returns NoneFix: returns 3
Gotcha 4: Returning the value that led with the largest count
Mistake
```
if count > best_count:
    best, best_count = candidate, count
```
Fix
```
return candidate
```
What happens: The lead changes as the pairs cancel. A value can hold the largest count early and still be paired off later. Only the candidate standing after the last value is the majority.
Example: nums = [1, 1, 2, 2, 2]
Mistake: returns 1Fix: returns 2

Deep Dive

Cancel different values in pairs

A majority value appears more than n / 2 times. Take any two different values and remove them together. This removes at most one copy of the majority value and at least one copy of another value.

The code does not store the pairs. It stores only candidate, the value that is not yet paired off, and count, the number of its copies that are not yet paired off. That is O(1) space.

Majority Element, traced on seven values

Take nums = [2, 2, 1, 1, 1, 2, 2]. candidate is None and count is 0.

The board marks the trap before the last step. The survivor is the answer only because a majority is promised. For nums = [1, 2, 3] the survivor is 3, and it occurs once.

Why the order of the two lines matters

The loop first tests count == 0, then updates count. When count is 0, every value read so far is paired off, so x starts a new run and counts as its own first copy.

With the right order, count never goes below 0.

Cost, and more than n / k

60-Second Pitch

Common Questions

Why does the majority value always survive?: Each cancellation removes two different values, so it removes at most one copy of the majority value. The majority value has more copies than all other values together. After all cancellations, copies of the majority value are still left, and everything that is left is one value.
What if there may be no majority value?: The survivor can then be any value. Count it in a second pass and return it only when nums.count(candidate) > len(nums) // 2. Otherwise return None. The second pass is still O(N) time and O(1) space.
How do you find values that appear more than n / 3 times?: Keep two candidates, each with its own count. A new value that equals one candidate adds a copy to it. A new value that equals neither takes a free slot if one exists, otherwise it subtracts one from both counts. Then count each candidate in a second pass. See Majority Element II (LC 229).
What does the final count mean?: It is the number of copies of candidate not yet paired off. It is not the number of times the value occurs. On [2, 2, 1, 1, 1, 2, 2] the final count is 1, and 2 occurs 4 times.
Why not use a hash map or sort the array?: A hash map of counts takes O(N) time but O(N) space. Sorting takes O(N log N) time, and the middle element is the majority. Voting takes O(N) time and O(1) space, which is why it is the expected answer when the memory limit matters.

SWE Reasoning

Spot it

A value holds more than a fixed share of the input (more than half, or more than n / k for a small k), as in Majority Element (LC 169) and Majority Element II (LC 229).
The answer must come in one pass with O(1) extra space, so a count per value is not allowed.
A majority is promised, or a second pass can check the survivor.

The invariant, step by step

candidate is None and count is 0. Nothing has been read.
For each x, if count == 0, everything read so far is paired off, so candidate = x.
Then count += 1 if x == candidate else -1. A matching value adds one copy. A different value cancels one copy and removes a pair of two different values.
Before each x, the values read so far, except count copies of candidate, are split into pairs of different values.
A pair contains at most one copy of the majority value, so the majority value cannot be cancelled out. It is the candidate after the last value.

Traps

Trusting the survivor without a promise. On [1, 2, 3] the survivor 3 occurs once. Count it in a second pass unless a majority is promised.
Looping over nums[:-1]. The last value is never read. On [1, 2, 2] the code returns 1 instead of 2.
Counting x before testing count == 0. On [3, 1, 3] the first value gives count = -1, and candidate stays None.
Returning the value with the largest count seen. The lead changes as pairs cancel. On [1, 1, 2, 2, 2] it returns 1 instead of 2.

Practice

Canonical LeetCode:Majority Element (LC 169)Majority Element II (LC 229)Minimum Index of a Valid Split (LC 2780)

Theory Context•Two Pointers & Sliding Window

P3MediumMental model~4 min speedrun

Boyer-Moore Voting (Majority Element)

Majority Element (LC 169)(opens leetcode.com)

Follow-up: can you find it in linear time with only O(1) extra space?

Example 1

Input:nums = [3,2,3]

Output:3

n = 3, so the majority needs more than 1 copy. 3 occurs twice.

Boyer-Moore Voting

Not this one if…

The array is sorted and the value to test is given, as in Check If a Number Is Majority Element in a Sorted Array (LC 1150): two binary searches find where its copies start and end, faster than any pass over the array. See Lower Bound

Boyer-Moore Voting

Python

1	def majority_element(nums: list[int]) -> int:
2	"""Majority Element: pair off different values; the majority is the value left standing.
3	Time: O(N) \| Space: O(1)
4	"""
5	# candidate, count: the value currently "standing" and how many of its copies are not yet
6	# paired off against a different value.
7	candidate, count = None, 0
8
9	# 1. Decide This Value's Role, Then Update The Tally:
10	# Everything read before a count of 0 is already paired off, so x starts a new run;
11	# counting after that check means x always counts as its own first copy, and count never
12	# goes below 0.
13	for x in nums:
14	if count == 0:
15	candidate = x
16	count += 1 if x == candidate else -1
17
18	# 2. Report The Value Left Standing:
19	# A value that fills more than half of nums has more copies than everything else combined,
20	# so pairing off different values can never cancel it; it is the one still standing at the end.
21	return candidate

Invariant: Before each x, the values read so far, except count copies of candidate, split into pairs of different values that cancel each other out.

See it run

Boyer-Moore Voting, step by step

candidate Nonecount 0

The top row is nums. The middle row is candidate after each value. The bottom row is count after each value.

x the value being read
candidate the value standing after this step
count its copies not yet paired off

Start: candidate is None and count is 0. nums has 7 values, and each one will add a copy or cancel one.

nums

candidate

count

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Returning candidate when no majority is promised
Mistake
```
return candidate
```
Fix
```
if nums.count(candidate) > len(nums) // 2:
    return candidate
return None
```
What happens: The last candidate is the majority only when a majority exists. Majority Element (LC 169) promises one, so the blueprint can return it. Without that promise, the survivor can be any value. Count it in a second pass before returning it.
Example: nums = [1, 2, 3], with no majority promised
Mistake: returns 3Fix: returns None
Gotcha 2: Looping over nums[:-1] and skipping the last value
Mistake
```
for x in nums[:-1]:
```
Fix
```
for x in nums:
```
What happens: Every value must cancel or add one copy. nums[:-1] leaves out the last value. When that value decides the result, the wrong candidate is left standing.
Example: nums = [1, 2, 2]
Mistake: returns 1Fix: returns 2
Gotcha 3: Counting x before testing count == 0
Mistake
```
count += 1 if x == candidate else -1
if count == 0:
    candidate = x
```
Fix
```
if count == 0:
    candidate = x
count += 1 if x == candidate else -1
```
What happens: When count is 0, every value read so far is paired off. The new value x must start the new run and count as its first copy. Counting first compares x with the old candidate. At the start, candidate is None, so the first value subtracts 1 and count becomes -1. count then never returns to 0, and candidate stays None.
Example: nums = [3, 1, 3]
Mistake: returns NoneFix: returns 3
Gotcha 4: Returning the value that led with the largest count
Mistake
```
if count > best_count:
    best, best_count = candidate, count
```
Fix
```
return candidate
```
What happens: The lead changes as the pairs cancel. A value can hold the largest count early and still be paired off later. Only the candidate standing after the last value is the majority.
Example: nums = [1, 1, 2, 2, 2]
Mistake: returns 1Fix: returns 2

Deep Dive

Cancel different values in pairs

A majority value appears more than n / 2 times. Take any two different values and remove them together. This removes at most one copy of the majority value and at least one copy of another value.

The code does not store the pairs. It stores only candidate, the value that is not yet paired off, and count, the number of its copies that are not yet paired off. That is O(1) space.

Majority Element, traced on seven values

Take nums = [2, 2, 1, 1, 1, 2, 2]. candidate is None and count is 0.

The board marks the trap before the last step. The survivor is the answer only because a majority is promised. For nums = [1, 2, 3] the survivor is 3, and it occurs once.

Why the order of the two lines matters

The loop first tests count == 0, then updates count. When count is 0, every value read so far is paired off, so x starts a new run and counts as its own first copy.

With the right order, count never goes below 0.

Cost, and more than n / k

60-Second Pitch

Common Questions

Why does the majority value always survive?: Each cancellation removes two different values, so it removes at most one copy of the majority value. The majority value has more copies than all other values together. After all cancellations, copies of the majority value are still left, and everything that is left is one value.
What if there may be no majority value?: The survivor can then be any value. Count it in a second pass and return it only when nums.count(candidate) > len(nums) // 2. Otherwise return None. The second pass is still O(N) time and O(1) space.
How do you find values that appear more than n / 3 times?: Keep two candidates, each with its own count. A new value that equals one candidate adds a copy to it. A new value that equals neither takes a free slot if one exists, otherwise it subtracts one from both counts. Then count each candidate in a second pass. See Majority Element II (LC 229).
What does the final count mean?: It is the number of copies of candidate not yet paired off. It is not the number of times the value occurs. On [2, 2, 1, 1, 1, 2, 2] the final count is 1, and 2 occurs 4 times.
Why not use a hash map or sort the array?: A hash map of counts takes O(N) time but O(N) space. Sorting takes O(N log N) time, and the middle element is the majority. Voting takes O(N) time and O(1) space, which is why it is the expected answer when the memory limit matters.

SWE Reasoning

Spot it

A value holds more than a fixed share of the input (more than half, or more than n / k for a small k), as in Majority Element (LC 169) and Majority Element II (LC 229).
The answer must come in one pass with O(1) extra space, so a count per value is not allowed.
A majority is promised, or a second pass can check the survivor.

The invariant, step by step

candidate is None and count is 0. Nothing has been read.
For each x, if count == 0, everything read so far is paired off, so candidate = x.
Then count += 1 if x == candidate else -1. A matching value adds one copy. A different value cancels one copy and removes a pair of two different values.
Before each x, the values read so far, except count copies of candidate, are split into pairs of different values.
A pair contains at most one copy of the majority value, so the majority value cannot be cancelled out. It is the candidate after the last value.

Traps

Trusting the survivor without a promise. On [1, 2, 3] the survivor 3 occurs once. Count it in a second pass unless a majority is promised.
Looping over nums[:-1]. The last value is never read. On [1, 2, 2] the code returns 1 instead of 2.
Counting x before testing count == 0. On [3, 1, 3] the first value gives count = -1, and candidate stays None.
Returning the value with the largest count seen. The lead changes as pairs cancel. On [1, 1, 2, 2, 2] it returns 1 instead of 2.

Practice

Canonical LeetCode:Majority Element (LC 169)Majority Element II (LC 229)Minimum Index of a Valid Split (LC 2780)

Theory Context•Two Pointers & Sliding Window

P3MediumMental model~4 min speedrun

Boyer-Moore Voting (Majority Element)

Majority Element (LC 169)(opens leetcode.com)

Follow-up: can you find it in linear time with only O(1) extra space?

Example 1

Input:nums = [3,2,3]

Output:3

n = 3, so the majority needs more than 1 copy. 3 occurs twice.

Boyer-Moore Voting

Not this one if…

The array is sorted and the value to test is given, as in Check If a Number Is Majority Element in a Sorted Array (LC 1150): two binary searches find where its copies start and end, faster than any pass over the array. See Lower Bound

Boyer-Moore Voting

Python

1	def majority_element(nums: list[int]) -> int:
2	"""Majority Element: pair off different values; the majority is the value left standing.
3	Time: O(N) \| Space: O(1)
4	"""
5	# candidate, count: the value currently "standing" and how many of its copies are not yet
6	# paired off against a different value.
7	candidate, count = None, 0
8
9	# 1. Decide This Value's Role, Then Update The Tally:
10	# Everything read before a count of 0 is already paired off, so x starts a new run;
11	# counting after that check means x always counts as its own first copy, and count never
12	# goes below 0.
13	for x in nums:
14	if count == 0:
15	candidate = x
16	count += 1 if x == candidate else -1
17
18	# 2. Report The Value Left Standing:
19	# A value that fills more than half of nums has more copies than everything else combined,
20	# so pairing off different values can never cancel it; it is the one still standing at the end.
21	return candidate

Invariant: Before each x, the values read so far, except count copies of candidate, split into pairs of different values that cancel each other out.

See it run

Boyer-Moore Voting, step by step

candidate Nonecount 0

The top row is nums. The middle row is candidate after each value. The bottom row is count after each value.

x the value being read
candidate the value standing after this step
count its copies not yet paired off

Start: candidate is None and count is 0. nums has 7 values, and each one will add a copy or cancel one.

nums

candidate

count

1 / 10

Gotchas1 of 4

The trap
Gotcha 1: Returning candidate when no majority is promised
Mistake
```
return candidate
```
Fix
```
if nums.count(candidate) > len(nums) // 2:
    return candidate
return None
```
What happens: The last candidate is the majority only when a majority exists. Majority Element (LC 169) promises one, so the blueprint can return it. Without that promise, the survivor can be any value. Count it in a second pass before returning it.
Example: nums = [1, 2, 3], with no majority promised
Mistake: returns 3Fix: returns None
Gotcha 2: Looping over nums[:-1] and skipping the last value
Mistake
```
for x in nums[:-1]:
```
Fix
```
for x in nums:
```
What happens: Every value must cancel or add one copy. nums[:-1] leaves out the last value. When that value decides the result, the wrong candidate is left standing.
Example: nums = [1, 2, 2]
Mistake: returns 1Fix: returns 2
Gotcha 3: Counting x before testing count == 0
Mistake
```
count += 1 if x == candidate else -1
if count == 0:
    candidate = x
```
Fix
```
if count == 0:
    candidate = x
count += 1 if x == candidate else -1
```
What happens: When count is 0, every value read so far is paired off. The new value x must start the new run and count as its first copy. Counting first compares x with the old candidate. At the start, candidate is None, so the first value subtracts 1 and count becomes -1. count then never returns to 0, and candidate stays None.
Example: nums = [3, 1, 3]
Mistake: returns NoneFix: returns 3
Gotcha 4: Returning the value that led with the largest count
Mistake
```
if count > best_count:
    best, best_count = candidate, count
```
Fix
```
return candidate
```
What happens: The lead changes as the pairs cancel. A value can hold the largest count early and still be paired off later. Only the candidate standing after the last value is the majority.
Example: nums = [1, 1, 2, 2, 2]
Mistake: returns 1Fix: returns 2

Deep Dive

Cancel different values in pairs

A majority value appears more than n / 2 times. Take any two different values and remove them together. This removes at most one copy of the majority value and at least one copy of another value.

The code does not store the pairs. It stores only candidate, the value that is not yet paired off, and count, the number of its copies that are not yet paired off. That is O(1) space.

Majority Element, traced on seven values

Take nums = [2, 2, 1, 1, 1, 2, 2]. candidate is None and count is 0.

The board marks the trap before the last step. The survivor is the answer only because a majority is promised. For nums = [1, 2, 3] the survivor is 3, and it occurs once.

Why the order of the two lines matters

The loop first tests count == 0, then updates count. When count is 0, every value read so far is paired off, so x starts a new run and counts as its own first copy.

With the right order, count never goes below 0.

Cost, and more than n / k

60-Second Pitch

Common Questions

Why does the majority value always survive?: Each cancellation removes two different values, so it removes at most one copy of the majority value. The majority value has more copies than all other values together. After all cancellations, copies of the majority value are still left, and everything that is left is one value.
What if there may be no majority value?: The survivor can then be any value. Count it in a second pass and return it only when nums.count(candidate) > len(nums) // 2. Otherwise return None. The second pass is still O(N) time and O(1) space.
How do you find values that appear more than n / 3 times?: Keep two candidates, each with its own count. A new value that equals one candidate adds a copy to it. A new value that equals neither takes a free slot if one exists, otherwise it subtracts one from both counts. Then count each candidate in a second pass. See Majority Element II (LC 229).
What does the final count mean?: It is the number of copies of candidate not yet paired off. It is not the number of times the value occurs. On [2, 2, 1, 1, 1, 2, 2] the final count is 1, and 2 occurs 4 times.
Why not use a hash map or sort the array?: A hash map of counts takes O(N) time but O(N) space. Sorting takes O(N log N) time, and the middle element is the majority. Voting takes O(N) time and O(1) space, which is why it is the expected answer when the memory limit matters.

SWE Reasoning

Spot it

A value holds more than a fixed share of the input (more than half, or more than n / k for a small k), as in Majority Element (LC 169) and Majority Element II (LC 229).
The answer must come in one pass with O(1) extra space, so a count per value is not allowed.
A majority is promised, or a second pass can check the survivor.

The invariant, step by step

candidate is None and count is 0. Nothing has been read.
For each x, if count == 0, everything read so far is paired off, so candidate = x.
Then count += 1 if x == candidate else -1. A matching value adds one copy. A different value cancels one copy and removes a pair of two different values.
Before each x, the values read so far, except count copies of candidate, are split into pairs of different values.
A pair contains at most one copy of the majority value, so the majority value cannot be cancelled out. It is the candidate after the last value.

Traps

Trusting the survivor without a promise. On [1, 2, 3] the survivor 3 occurs once. Count it in a second pass unless a majority is promised.
Looping over nums[:-1]. The last value is never read. On [1, 2, 2] the code returns 1 instead of 2.
Counting x before testing count == 0. On [3, 1, 3] the first value gives count = -1, and candidate stays None.
Returning the value with the largest count seen. The lead changes as pairs cancel. On [1, 1, 2, 2, 2] it returns 1 instead of 2.

Practice

Canonical LeetCode:Majority Element (LC 169)Majority Element II (LC 229)Minimum Index of a Valid Split (LC 2780)