MediumDSA10 min read

Longest consecutive sequence in O(n) with hash set — why not sort?

Q: Longest consecutive sequence in O(n) with hash set — why not sort?

**Target Audience:** Intermediate candidates — you should know arrays and what a hash set does; Big-O basics help. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown in the **Verified** section was produced by actually running the Python code with `python3 main.py`; nothing is quoted from memory. ## 1. Why This Even Matters — A Story First Imagine a deck of cards with numbers on them, shuffled and with some cards missing and some duplicated. You want the longest straight: the most numbers in a row, like 4-5-6-7. The obvious way is to sort the deck first and then read off the runs. That works, but sorting a big deck is the slow part. A faster trick: spread the cards on a table where you can instantly check whether any number is present. Now pick up a card, say 5, and ask one question: "is 4 on the ta

142 views

121 of 154

The problem

Question presented to candidate: "Given an unsorted list of integers, return the length of the longest run of consecutive values, in O(n) time. Then tell me why you did not just sort it. Use Python."

What a strong answer should cover:

Build a set, and only start counting from x when x - 1 is not in the set.
Why it is O(n): each number is walked over at most once, about 2n lookups in total (amortized).
Why not sort: O(n log n) does more work than needed; trade-offs in memory, worst case and constants.
Python specifics: iterate the set, not the list, so duplicates are not re-checked; in on a set is average O(1) but on a list is O(n).
Edge cases: empty list, duplicates, negatives.

Clarifying questions expected:

"Can there be duplicates, and should an empty array return 0?"
"Is O(n log n) acceptable, or is O(n) required?" — the whole point of the question.

Code / implementation expected: Yes — a short Python function using set.

hash set
array
Meta

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Intermediate candidates — you should know arrays and what a hash set does; Big-O basics help. Difficulty: Medium Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown in the Verified section was produced by actually running the Python code with python3 main.py; nothing is quoted from memory.

1. Why This Even Matters — A Story First

Imagine a deck of cards with numbers on them, shuffled and with some cards missing and some duplicated. You want the longest straight: the most numbers in a row, like 4-5-6-7. The obvious way is to sort the deck first and then read off the runs. That works, but sorting a big deck is the slow part.

A faster trick: spread the cards on a table where you can instantly c

The solution is hidden so you can try first

10 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonHash set and sorting on six inputs

Practice

PythonCounting lookups: with and without the start check

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 121 of 154 in DSA

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All DSA questions

Up nextMedium→

What are the most useful bit manipulation tricks for interviews?

Continue