Builds on Hash Map, which you haven’t finished yet.
Start-Element Pruning (Longest Consecutive Sequence)
You get an integer array nums, in no particular order. A run is a chain of whole numbers that each exceed the one before by exactly 1 (x, x + 1, x + 2, ...). Find the longest run whose values all appear somewhere in nums, at any positions, and return how many values it holds.
Your algorithm has to finish in O(n) time.
[1, 2, 3, 4] holds 4 values.Hash-Set Sequence Scanning
nums -> seen = set(nums) -> walk upward only from a run's startO(n) time", "longest consecutive". Sorting is ruled out by the time budget, and the real question is "is the next value present?", which a hash set answers in one lookup -- but a plain lookup from every value is still O(N^2) on one long run, so the model also needs a cheap way to know which values are worth walking from.| 1 | def longestConsecutive(nums: list[int], delta: int = 1) -> int: |
| 2 | """Finds the length of the longest arithmetic run with common difference `delta`. |
| 3 | Called with the default delta=1, this is exactly LC 128's algorithm; LeetCode's |
| 4 | harness calls it with only `nums`, so the extra parameter never breaks the signature. |
| 5 | Time: O(N) | Space: O(N) |
| 6 | """ |
| 7 | if not nums: |
| 8 | return 0 |
| 9 | Â |
| 10 | seen = set(nums) # O(N) deduplication & constant-time lookups |
| 11 | best = 0 |
| 12 | Â |
| 13 | for left in seen: |
| 14 | # Step 1: Start-Element Pruning |
| 15 | # If 'left - delta' exists, 'left' sits inside a run and cannot be the head. |
| 16 | if left - delta in seen: |
| 17 | continue |
| 18 | Â |
| 19 | # Step 2: Count Progression Steps from Head |
| 20 | # 'length' counts the total number of valid terms in the progression. |
| 21 | length = 1 |
| 22 | while left + length * delta in seen: |
| 23 | length += 1 |
| 24 | Â |
| 25 | # Step 3: Record Maximum Count |
| 26 | best = max(best, length) |
| 27 | Â |
| 28 | return best |
left - delta is absent from seen, so every value is visited by the upward walk of at most one run.A run of consecutive values has exactly one smallest member, and that member is the only one in the run whose predecessor is missing from seen, so if left - delta in seen: continue finds every run's start in one lookup and only a start is ever walked upward. Across the whole array, every value is checked once by the for loop and walked past by at most one run's while loop -- the one it belongs to. The trap: walking the upward probe from every value, not only from run starts, re-walks every run once per value inside it -- the pruning check is what keeps every value visited by at most one walk.
See it run
Start-Element Pruning, step by step
left -length -probe -best 0probes 0
The top row is nums. The bottom row shows the run length under the start of each run. The loop takes the values in the order of nums.
lefta value that starts a run, because left - delta is not in seenskipa value inside a run, skipped because left - delta is in seennexta value found by the upward walklengththe length of the run that starts at left
Start: seen holds the 6 distinct values of nums. The loop looks at each value as left.
Gotcha 1 of 4
- The trap
Gotcha 1: Skipping the start-element pruning check (the card's trap)
Mistakefor left in seen: length = 1 while left + length * delta in seen: length += 1 best = max(best, length)Fixif left - delta in seen: continueWhat happens: Without the pruning check, the walk starts from every value, not only from a run's start. Every value inside an N-long run then re-walks the same run from its own position. One run of length N alone costs about N^2 lookups instead of N. The problem's
O(n)requirement forbids this.
- Both models build a hash structure over every item once, but Group Anagrams (LC 49) groups items that share a computed key; Hash-Set Sequence Scanning instead prunes which values are worth walking from, and only walks upward from a run's start. See Hash Map
- Longest Arithmetic Subsequence of Given Difference (LC 1218) asks for the same one-step neighbour,
v - difference, but it wants a subsequence, and a subsequence must keep the order of the positions inarr. Switch cards as soon as the problem says subsequence or in order: Hash-Set Sequence Scanning readsseenand ignores positions, so on[1, 3, 2]with difference 1 it would answer 3, where the correct answer is 2 (3comes before2inarr, so[1, 2, 3]is not a subsequence). See LIS
Deep Dive
The set answers "is the next value there?", but not "where should I start?"
Count and Lookup already gives the tool: seen = set(nums) answers "is this value present?" in one step. A run is a chain of values with a fixed step delta between neighbours, and the step test is left + length * delta in seen.
That is not enough. If the walk starts from every value, a run of N values is walked from its first value (N steps), from its second (N - 1 steps), and so on. The total is about N^2 / 2 lookups. The problem asks for O(n).
The extra idea of this card is a cheap test for which values are worth walking from. Every run has exactly one smallest value. That value is the only one in its run whose predecessor left - delta is missing from seen.
So if left - delta in seen: continue finds every run's start with one lookup. The loop then walks upward from starts only.
Traced on [100, 4, 200, 1, 3, 2]
seen is {100, 4, 200, 1, 3, 2} and delta = 1. The board takes the values in the order of nums. The Python set may iterate in another order, and the answer is the same.
left = 100: 99 is not in seen, so 100 is a start. 101 is not in seen, so length = 1. left = 4: 3 is in seen, so 4 is skipped.
left = 200: 199 is not in seen, so 200 is a start, and 201 is absent, so length = 1. left = 1: 0 is not in seen, so 1 is a start. The walk finds 2, 3 and 4, then 5 is absent. So length = 4 and best = 4.
left = 3 and left = 2 are skipped, because 2 and 1 are in seen. The result is 4, for the run 1, 2, 3, 4.
The walks used 6 probes. If every value had walked upward, the same example would use 12. For one run of 1000 values, the walk from every value makes 499,500 successful probes. The pruned loop makes about 1,000 probes plus 1,000 start checks.
Why every value is walked at most once
A walk starts only at a run's smallest value. Each value belongs to exactly one run, so it is passed over by at most one walk: the walk of its own run.
The for loop checks each value once. The while loops together probe every value of every run once, plus one failed probe per run. Both counts are at most 2N, so the time is O(N). The set costs O(N) space.
Duplicates need no work. A set keeps one copy of each value, so [1, 0, 1, 2] has the run 0, 1, 2 of length 3. Counting the repeated 1 as a second step would return 4.
best = max(best, length) keeps the longest run so far. best = length would let a later short run erase the answer. For [1, 2, 3, 10, 11] it returns 2 instead of 3.
The delta parameter
The blueprint generalises the step to delta. The next term after length terms is left + length * delta. With delta = 1 this is Longest Consecutive Sequence (LC 128).
Dropping the factor, left + length, silently uses a step of 1. For [2, 4, 6, 8] and delta = 2, the right answer is 4 and the wrong test gives 1.
The start test uses the same step: left - delta. If the start test and the walk used different steps, a run could be skipped or walked twice.
60-Second Pitch
"Sorting costs O(N log N), so I use a set. The question of whether the next value is there is one lookup. A walk from every value would still cost O(N^2) on one long run. So I walk only from the start of a run. A value is a start when left - delta is not in the set. For a start I count upward while left + length * delta is in the set, and I keep the maximum length. Each value is passed over by at most one walk, so the time is O(N) and the space is O(N) for the set."
Common Questions
- Why is a loop inside a loop still
O(N)? The inner
whileruns only from run starts. Each value belongs to one run, so the inner loops together probe each value once, plus one failed probe per run. The inner work is shared across the outer loop, not repeated.- Why use a set instead of sorting?
Sorting costs
O(N log N), and the problem requiresO(n). A set costsO(N)to build and answers each "is the next value present?" in constant time on average.- What happens with duplicate values?
The set keeps one copy of each value, so duplicates do not change any run.
[1, 0, 1, 2]has the run0, 1, 2and the answer 3.- What does the card add to Count and Lookup?
Count and Lookup gives the set and the constant-time lookup. This card adds the test
left - delta in seen, which decides where a walk may start. Without the test, the lookups alone still costO(N^2)on one long run.- Could Union-Find solve the same problem?
Yes. Join each value with its neighbour
value + 1when that neighbour is present, and take the largest set size. It also runs in near-linear time. The set with start pruning needs less code and no extra structure.
SWE Reasoning
Spot it
- "Unsorted array", "longest consecutive" and "must run in
O(n)time" appear together (Longest Consecutive Sequence (LC 128)). - Sorting would take
O(N log N), so the question has to be answered by lookups. - A run has one start, and the start can be recognised by one lookup of its predecessor.
- A plain lookup walk from every value is still
O(N^2)on one long run.
The invariant, step by step
seen = set(nums)removes duplicates and gives constant-time lookups.- For each
leftinseen, testleft - delta in seen. If it is there,leftis inside a run, and the loop continues. - Otherwise
leftis the smallest value of its run. Setlength = 1. - While
left + length * delta in seen, add 1 tolength. The walk visits only values of this run. best = max(best, length)keeps the longest run.- Every value is walked by at most one run, so the total work is
O(N).
Traps
- No pruning test. Every value walks upward. One run of
Nvalues costs aboutN^2 / 2lookups, which breaks theO(n)requirement. - Counting repeats.
length += counts[x]makes[1, 0, 1, 2]return 4 instead of 3. best = length. A later, shorter run erases the answer.[1, 2, 3, 10, 11]returns 2 instead of 3.left + lengthwithoutdelta. Anydeltaother than 1 probes the wrong values.
Practice
Builds on Hash Map, which you haven’t finished yet.
Start-Element Pruning (Longest Consecutive Sequence)
You get an integer array nums, in no particular order. A run is a chain of whole numbers that each exceed the one before by exactly 1 (x, x + 1, x + 2, ...). Find the longest run whose values all appear somewhere in nums, at any positions, and return how many values it holds.
Your algorithm has to finish in O(n) time.
[1, 2, 3, 4] holds 4 values.Hash-Set Sequence Scanning
nums -> seen = set(nums) -> walk upward only from a run's startO(n) time", "longest consecutive". Sorting is ruled out by the time budget, and the real question is "is the next value present?", which a hash set answers in one lookup -- but a plain lookup from every value is still O(N^2) on one long run, so the model also needs a cheap way to know which values are worth walking from.| 1 | def longestConsecutive(nums: list[int], delta: int = 1) -> int: |
| 2 | """Finds the length of the longest arithmetic run with common difference `delta`. |
| 3 | Called with the default delta=1, this is exactly LC 128's algorithm; LeetCode's |
| 4 | harness calls it with only `nums`, so the extra parameter never breaks the signature. |
| 5 | Time: O(N) | Space: O(N) |
| 6 | """ |
| 7 | if not nums: |
| 8 | return 0 |
| 9 | Â |
| 10 | seen = set(nums) # O(N) deduplication & constant-time lookups |
| 11 | best = 0 |
| 12 | Â |
| 13 | for left in seen: |
| 14 | # Step 1: Start-Element Pruning |
| 15 | # If 'left - delta' exists, 'left' sits inside a run and cannot be the head. |
| 16 | if left - delta in seen: |
| 17 | continue |
| 18 | Â |
| 19 | # Step 2: Count Progression Steps from Head |
| 20 | # 'length' counts the total number of valid terms in the progression. |
| 21 | length = 1 |
| 22 | while left + length * delta in seen: |
| 23 | length += 1 |
| 24 | Â |
| 25 | # Step 3: Record Maximum Count |
| 26 | best = max(best, length) |
| 27 | Â |
| 28 | return best |
left - delta is absent from seen, so every value is visited by the upward walk of at most one run.A run of consecutive values has exactly one smallest member, and that member is the only one in the run whose predecessor is missing from seen, so if left - delta in seen: continue finds every run's start in one lookup and only a start is ever walked upward. Across the whole array, every value is checked once by the for loop and walked past by at most one run's while loop -- the one it belongs to. The trap: walking the upward probe from every value, not only from run starts, re-walks every run once per value inside it -- the pruning check is what keeps every value visited by at most one walk.
See it run
Start-Element Pruning, step by step
left -length -probe -best 0probes 0
The top row is nums. The bottom row shows the run length under the start of each run. The loop takes the values in the order of nums.
lefta value that starts a run, because left - delta is not in seenskipa value inside a run, skipped because left - delta is in seennexta value found by the upward walklengththe length of the run that starts at left
Start: seen holds the 6 distinct values of nums. The loop looks at each value as left.
Gotcha 1 of 4
- The trap
Gotcha 1: Skipping the start-element pruning check (the card's trap)
Mistakefor left in seen: length = 1 while left + length * delta in seen: length += 1 best = max(best, length)Fixif left - delta in seen: continueWhat happens: Without the pruning check, the walk starts from every value, not only from a run's start. Every value inside an N-long run then re-walks the same run from its own position. One run of length N alone costs about N^2 lookups instead of N. The problem's
O(n)requirement forbids this.
- Both models build a hash structure over every item once, but Group Anagrams (LC 49) groups items that share a computed key; Hash-Set Sequence Scanning instead prunes which values are worth walking from, and only walks upward from a run's start. See Hash Map
- Longest Arithmetic Subsequence of Given Difference (LC 1218) asks for the same one-step neighbour,
v - difference, but it wants a subsequence, and a subsequence must keep the order of the positions inarr. Switch cards as soon as the problem says subsequence or in order: Hash-Set Sequence Scanning readsseenand ignores positions, so on[1, 3, 2]with difference 1 it would answer 3, where the correct answer is 2 (3comes before2inarr, so[1, 2, 3]is not a subsequence). See LIS
Deep Dive
The set answers "is the next value there?", but not "where should I start?"
Count and Lookup already gives the tool: seen = set(nums) answers "is this value present?" in one step. A run is a chain of values with a fixed step delta between neighbours, and the step test is left + length * delta in seen.
That is not enough. If the walk starts from every value, a run of N values is walked from its first value (N steps), from its second (N - 1 steps), and so on. The total is about N^2 / 2 lookups. The problem asks for O(n).
The extra idea of this card is a cheap test for which values are worth walking from. Every run has exactly one smallest value. That value is the only one in its run whose predecessor left - delta is missing from seen.
So if left - delta in seen: continue finds every run's start with one lookup. The loop then walks upward from starts only.
Traced on [100, 4, 200, 1, 3, 2]
seen is {100, 4, 200, 1, 3, 2} and delta = 1. The board takes the values in the order of nums. The Python set may iterate in another order, and the answer is the same.
left = 100: 99 is not in seen, so 100 is a start. 101 is not in seen, so length = 1. left = 4: 3 is in seen, so 4 is skipped.
left = 200: 199 is not in seen, so 200 is a start, and 201 is absent, so length = 1. left = 1: 0 is not in seen, so 1 is a start. The walk finds 2, 3 and 4, then 5 is absent. So length = 4 and best = 4.
left = 3 and left = 2 are skipped, because 2 and 1 are in seen. The result is 4, for the run 1, 2, 3, 4.
The walks used 6 probes. If every value had walked upward, the same example would use 12. For one run of 1000 values, the walk from every value makes 499,500 successful probes. The pruned loop makes about 1,000 probes plus 1,000 start checks.
Why every value is walked at most once
A walk starts only at a run's smallest value. Each value belongs to exactly one run, so it is passed over by at most one walk: the walk of its own run.
The for loop checks each value once. The while loops together probe every value of every run once, plus one failed probe per run. Both counts are at most 2N, so the time is O(N). The set costs O(N) space.
Duplicates need no work. A set keeps one copy of each value, so [1, 0, 1, 2] has the run 0, 1, 2 of length 3. Counting the repeated 1 as a second step would return 4.
best = max(best, length) keeps the longest run so far. best = length would let a later short run erase the answer. For [1, 2, 3, 10, 11] it returns 2 instead of 3.
The delta parameter
The blueprint generalises the step to delta. The next term after length terms is left + length * delta. With delta = 1 this is Longest Consecutive Sequence (LC 128).
Dropping the factor, left + length, silently uses a step of 1. For [2, 4, 6, 8] and delta = 2, the right answer is 4 and the wrong test gives 1.
The start test uses the same step: left - delta. If the start test and the walk used different steps, a run could be skipped or walked twice.
60-Second Pitch
"Sorting costs O(N log N), so I use a set. The question of whether the next value is there is one lookup. A walk from every value would still cost O(N^2) on one long run. So I walk only from the start of a run. A value is a start when left - delta is not in the set. For a start I count upward while left + length * delta is in the set, and I keep the maximum length. Each value is passed over by at most one walk, so the time is O(N) and the space is O(N) for the set."
Common Questions
- Why is a loop inside a loop still
O(N)? The inner
whileruns only from run starts. Each value belongs to one run, so the inner loops together probe each value once, plus one failed probe per run. The inner work is shared across the outer loop, not repeated.- Why use a set instead of sorting?
Sorting costs
O(N log N), and the problem requiresO(n). A set costsO(N)to build and answers each "is the next value present?" in constant time on average.- What happens with duplicate values?
The set keeps one copy of each value, so duplicates do not change any run.
[1, 0, 1, 2]has the run0, 1, 2and the answer 3.- What does the card add to Count and Lookup?
Count and Lookup gives the set and the constant-time lookup. This card adds the test
left - delta in seen, which decides where a walk may start. Without the test, the lookups alone still costO(N^2)on one long run.- Could Union-Find solve the same problem?
Yes. Join each value with its neighbour
value + 1when that neighbour is present, and take the largest set size. It also runs in near-linear time. The set with start pruning needs less code and no extra structure.
SWE Reasoning
Spot it
- "Unsorted array", "longest consecutive" and "must run in
O(n)time" appear together (Longest Consecutive Sequence (LC 128)). - Sorting would take
O(N log N), so the question has to be answered by lookups. - A run has one start, and the start can be recognised by one lookup of its predecessor.
- A plain lookup walk from every value is still
O(N^2)on one long run.
The invariant, step by step
seen = set(nums)removes duplicates and gives constant-time lookups.- For each
leftinseen, testleft - delta in seen. If it is there,leftis inside a run, and the loop continues. - Otherwise
leftis the smallest value of its run. Setlength = 1. - While
left + length * delta in seen, add 1 tolength. The walk visits only values of this run. best = max(best, length)keeps the longest run.- Every value is walked by at most one run, so the total work is
O(N).
Traps
- No pruning test. Every value walks upward. One run of
Nvalues costs aboutN^2 / 2lookups, which breaks theO(n)requirement. - Counting repeats.
length += counts[x]makes[1, 0, 1, 2]return 4 instead of 3. best = length. A later, shorter run erases the answer.[1, 2, 3, 10, 11]returns 2 instead of 3.left + lengthwithoutdelta. Anydeltaother than 1 probes the wrong values.