Longest Consecutive Sequence
From a 22-minute DSA round · calibrated to L5
22m
Duration
5
Key moments
5
Strengths
4
Focus areas
Summary
The candidate tackled the Longest Consecutive Sequence problem cleanly and efficiently in a 19-minute session. They opened with appropriate clarifying questions (value range, array size), correctly ruled out a counting array due to the ±1B range, and converged on the canonical hash-set approach. The core insight — only walk from run starts to achieve amortized O(n) — was stated correctly and defended with a precise argument: runs don't overlap, so total walk steps equal the sum of run lengths, which is bounded by the number of distinct elements. The code on the page is correct, readable, and matches the verbal explanation.
The session had one meaningful stumble: the candidate initially mis-stated the brute force as O(n) rather than O(n²), and separately wrote the skip condition inverted (x+1 instead of x-1) before catching it during the dry run. Both errors were self-corrected quickly and without significant prompting, which is a positive signal — the candidate traces logic rather than just asserting answers. The follow-up on returning the actual sequence (store start + length, reconstruct with range) was handled fluently, including correct complexity analysis of the reconstruction step.
Overall this is a confident L5-caliber performance. The candidate demonstrates genuine algorithmic understanding, clean reasoning under pressure, and good instincts for constraint-driven design decisions. The main growth area is front-loading more rigorous complexity verification and edge-case enumeration before writing code, rather than discovering issues during the dry run.
Coach's note
This candidate demonstrated solid L5-level DSA competency: they arrived at the canonical O(n) hash-set solution with a clean amortized correctness argument, handled all edge cases correctly, and showed strong self-debugging instincts when their dry run exposed a logic inversion. The one notable hiccup — initially mis-stating the brute force complexity as O(n) — was quickly corrected under light interviewer pressure, and the candidate showed genuine understanding rather than just pattern-matching to a known solution. Recommend advancing to the next round.
Performance breakdown
Strengths
- Immediately ruled out a counting array due to value range constraints — proactive constraint reasoning before writing a single line of code
- Correctly identified and articulated the amortized O(n) argument: walks only start at run starts, runs don't overlap, so total walk steps = sum of run lengths ≤ d ≤ n
- Self-corrected the inverted skip condition during dry run without needing the interviewer to explain the fix — just traced the logic and caught the bug
- Clean, minimal code on the page: well-named variables, correct structure, no unnecessary complexity
- Handled the 'return the actual sequence' follow-up elegantly — recognized that storing only (start, length) avoids building throwaway lists, and correctly analyzed the O(L) reconstruction cost
Areas to improve
- Initial brute force complexity claim was wrong (stated O(n) instead of O(n²)) — should stress-test complexity claims with a concrete adversarial example before asserting them
- First dry run had the skip condition inverted (checking x+1 instead of x-1), suggesting the code was written slightly ahead of careful verification; a slower trace before writing would catch this
- Could have been more precise upfront about the amortized argument — the interviewer had to prompt for the formal justification rather than the candidate volunteering it proactively
- Edge case coverage was good but reactive (prompted by interviewer) rather than fully self-driven; an L5 candidate ideally enumerates edge cases unprompted before the dry run
Key moments
counting array is out, that's way too big to allocate. and n is a hundred thousand so a set is fine memory wise.
Immediately after receiving the value range constraint, the candidate ruled out a counting/bucket array approach due to the ±1B range — demonstrating proactive constraint-driven reasoning before writing any code.
i'd dump everything into a set, then for each number walk forward x plus one, x plus two, while they're in the set and keep the longest. and set lookups are constant so, uh, that's O of n i think.
The candidate incorrectly stated the brute force complexity as O(n) rather than O(n²). This is a meaningful error — the interviewer had to prompt with a concrete adversarial example before the candidate self-corrected.
wait. umm. that gives me best equals one, but the answer should obviously be three, one two three is right there. so something's off. hold on.
During the dry run, the candidate immediately recognized the output was wrong and began tracing the logic — demonstrating debugging instincts and willingness to question their own code rather than rationalize an incorrect result.
walks only ever start at a run start, and runs don't overlap each other. so if you add up the walk steps across every run, you're really just adding up the run lengths, and each distinct value sits in exactly one run. so the total is d, which is at most n.
When pressed for a precise amortized argument, the candidate delivered a clean, correct, and complete justification — not just asserting linearity but proving it via the non-overlapping runs partition argument.
the reason i don't need to store the actual list as i go is that a run is contiguous by definition, so the start plus the length is enough to regenerate it. saves me building throwaway lists for runs that lose.
On the follow-up extension question, the candidate proactively identified a space optimization (store start+length, not the list itself) and articulated the reasoning — showing design sensibility beyond just correctness.
Watch-outs
- Mis-stated brute force complexity as O(n) without stress-testing the claim — required interviewer prompting to correct; at L5, complexity claims should be verified before stating them
- Skip condition was written inverted in the first pass (x+1 instead of x-1), suggesting code was written slightly ahead of careful logical verification
Questions to practice next
- If the array could contain up to 10^9 elements (not just 10^5), how would your space analysis change, and would you consider any alternative approaches?
- How would you adapt this solution if the problem required finding all consecutive sequences of length ≥ k, not just the longest one?
- Can you walk me through how Python's set handles hash collisions, and in what adversarial input scenario could your O(n) solution degrade in practice?
- If this were a streaming problem — integers arriving one at a time — how would you maintain the longest consecutive sequence length incrementally?
- You mentioned iterating over the set rather than the original array to avoid duplicate work. Are there any correctness or performance edge cases where iterating over the array instead might actually be preferable?
Code & notes
Final Approach: The candidate used a hash set for O(1) membership lookups, iterating over the set and only initiating forward walks from elements with no left neighbor (x-1 not in set). This is the canonical O(n) solution to the Longest Consecutive Sequence problem and exactly matches what was discussed verbally.
Correctness: The final code on the page is correct. The initial version had the skip condition inverted (if x - 1 in s: continue was originally written as checking x + 1), but this was caught during the dry run and corrected on the page. The corrected version handles all cases: empty input (set is empty, loop never runs, returns 0), duplicates (set deduplication), negatives (arithmetic is sign-agnostic), and single-element runs. The bonus extension (tracking best_start to return the actual sequence) is also correctly sketched.
Completeness: The page is impressively complete for a 19-minute session. It contains: a problem restatement with constraints, a brute force with explicit complexity analysis and a worked counterexample showing why it's O(n²), the optimized solution with the key insight stated, a first (incorrect) dry run, a corrected dry run, a formal complexity argument (including the amortized walk-step bound), three edge cases with traces, and a sketch of the sequence-return extension. This is well above average completeness.
Code Quality: The code is clean and idiomatic Python. Variable names (s, best, cur, y, x) are concise but unambiguous in context. The structure is minimal — no unnecessary scaffolding. The page is organized top-to-bottom in a logical flow (problem → brute → fix → code → dry run → complexity → edge cases → extension), which reflects disciplined thinking.
Notable Decisions: The candidate explicitly noted iterating over s (the set) rather than nums (the original array) to avoid redundant work from duplicates — a subtle but correct optimization that not all candidates catch. The reconstruction extension correctly avoids storing intermediate run lists, instead relying on the contiguity property to regenerate the answer from (start, length) — this is a space-conscious design choice worth noting positively.
LONGEST CONSEC SEQ
given:
- unsorted
- dups count once
- [] -> 0
- O(n), no sorting
ask:
- range = -1e9 .. 1e9
- n <= 1e5
brute:
s = set(nums)
for x in nums:
walk x+1, x+2... while in s
keep max
-> O(n^2) NOT O(n)
1..n : walk n, then n-1, then n-2 ...
fix: only walk from the START of a run
def longest(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 in s:
continue
cur = 1
y = x + 1
while y in s:
cur += 1
y += 1
best = max(best, cur)
return best
dry run: [1,2,3,100]
s = {1,2,3,100}
x=1 : 2 in s -> skip
x=2 : 3 in s -> skip
x=3 : 4 not in s -> walk, cur=1
x=100: 101 not in s -> cur=1
best = 1
redo dry run: [1,2,3,100]
x=1 : 0 not in s -> START, walk 2,3 -> cur=3
x=2 : 1 in s -> skip
x=3 : 2 in s -> skip
x=100: 99 not in s -> START, cur=1
best = 3 ok
complexity:
time O(n) set build + each elem touched <= 2x
space O(d) d = distinct vals, <= n
why walks total <= n:
walks only start at run starts, runs dont overlap
sum of all walk steps = sum of run lengths = d <= n
edge cases:
[] -> set empty, for loop never runs, best stays 0. ok, no guard needed
[2,2,2] -> s={2}, 1 not in s -> START, 3 not in s -> cur=1. ok
[-1,0,1]-> -2 not in s -> START, walks 0,1 -> 3. negatives fine
return the run itself:
keep best_start too
if cur > best:
best = cur
best_start = x
return list(range(best_start, best_start + best)) if best else []
(dont store the run - its contiguous, so start+len regenerates it)This took 42 minutes and cost nothing.
Two free mock interviews every cycle — no card, no scheduling, no waiting for a human to be available. Sit one now and get a report like this.
Take a free mock