vizlearn

Longest consecutive sequence

Interview QuestionsBy Updated

Put everything in a set, then only start counting from a value whose predecessor is absent. That single check is what keeps it O(n): every run is walked exactly once, from its start, so the inner loop across the whole input does n steps in total rather than n per element.

Dicts, sets & hashingCoding problemMedium

Step through it

What to watch

  • Values with a predecessor present are skipped without any work.
  • Each run is walked exactly once, from its lowest member.
  • The input is never sorted.

Say this out loud

"Set for O(1) membership, then for each value check whether value-1 is in the set. If it is, skip - something else starts that run. If it isn't, walk forward. Every element is visited at most twice, so O(n)."

Longest consecutive sequence

Find the length of the longest run of consecutive integers in an unsorted array, in O(n).

Why not just sort

Sorting makes it trivial — one pass counting adjacent runs — and costs O(n log n). The question asks for O(n) specifically to rule that out, so give the sorting answer, name its cost, and then improve it.

The check that makes it linear

Without the start-of-run test, each value walks its whole run and the work is quadratic on a long sequence. With it, a value only walks forward when value - 1 is absent — and each run has exactly one such value.

So across the entire input the inner loop takes as many steps as there are elements, not as many as elements times run length. Every element is touched at most twice: once in the outer loop, once by the walk of its own run.

Saying the complexity convincingly

This is the question where candidates write the right code and then call it O(n²) because there is a loop inside a loop. The argument to make out loud is amortised: the inner loop's total work across all iterations is bounded by n, because runs do not overlap.

Same shape as the sliding window, where both pointers only move forward. A nested loop is not automatically quadratic; what matters is how many times the inner body can run in total.

Run it in Python

The O(n) version with its inner-loop steps counted against the version missing the start check, on an input built to make the difference obvious.

consecutive.pyPython 3
Output
How the code works
  1. if v - 1 in pool: continueThe line the whole complexity rests on. A value with a predecessor is somewhere in the middle of a run that another value will walk, so doing anything here is pure duplication.
  2. while v + length in pool:A nested loop that is not quadratic. Runs do not overlap, so the total number of inner steps across the whole outer loop is bounded by n.
  3. pool = set(values)Membership has to be O(1) for any of this to work. On a list the same code would be O(n²) at best.
  4. for v in poolIterating the set rather than the list also removes duplicate work when the input repeats values.
Change one thing
  • Iterate values instead of pool on an input with many duplicates. Same answer, more work.
  • Return the run itself rather than its length by remembering v when best improves.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. What makes the solution O(n) despite a loop inside a loop?
  2. How do you know a value starts a run?
  3. Why is sorting not the accepted answer?





 Cheat sheet
Longest consecutive sequence
Put everything in a set, then only start counting from a value whose predecessor is absent. That single check is what keeps it O(n): every run is walked exactly once, from its start, so the inner loop across the whole input does n steps in total rather than n per element.
INTERVIEW · vizlearn.in/interview/longest-consecutive-sequence.html
More in Interview
InterviewSubarray sum equals kInterviewWhen should you use a set instead of a list?InterviewWhat happens if you modify a collection while looping over it?InterviewMemoisation: caching with a dictionary
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact