DSA interview question

Longest Consecutive Sequence

Medium · Algorithms · Topics: array, hash set, union find

The problem

A game logs the levels players have completed, in no particular order and with repeats, and the achievements screen wants the longest streak of consecutive level numbers a player has cleared (such as 1, 2, 3, 4) no matter what order they played them in. Sorting and scanning is O(n log n). The O(n) trick uses a hash set: only start counting from numbers that begin a streak (their predecessor isn't in the set), and walk upwards from there. Every number is then visited a constant number of times.

Example: [100, 4, 200, 1, 3, 2] → 4 (the sequence 1, 2, 3, 4).

Function signature

int longestConsecutive(const vector<int>& nums);  // length of the longest run of consecutive integers

Test cases

Input `nums`	Output	Explanation
`[100, 4, 200, 1, 3, 2]`	4	1, 2, 3, 4
`[0, 3, 7, 2, 5, 8, 4, 6, 0, 1]`	9	0 through 8; the duplicate 0 doesn't matter
`[1, 2, 0, 1]`	3	0, 1, 2
`[-1, -2, 5]`	2	-2, -1
`[9]`	1
`[]`	0

(Confirm: the elements don't need to be adjacent in the array; duplicates count once; O(n) time is expected.)

How interviewers phrase it

"Find the length of the longest consecutive elements sequence in O(n)" (LeetCode 128).
Asked to test whether you can beat the obvious sort-based O(n log n) solution.

Clarifying questions to ask

Do the numbers have to be adjacent in the array? (No: it's about values.)
How are duplicates treated?
Is O(n log n) acceptable, or must it be O(n)?

Follow-ups to expect

"What's the sorting solution?"
"Why only start from numbers whose predecessor is missing?"
"Why is it O(n) with a nested while loop?"
"Could you use union-find?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview