Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm must run in O(n) time.
For example, given nums = [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so the answer is 4.
Explain your approach, why it achieves O(n) time despite appearing to have nested loops, and discuss edge cases.
How to approach it
- Hint 1
Sorting would give O(n log n). To get O(n), think about hash sets for O(1) lookups.
- Hint 2
For each number, you could try to extend a sequence. But how do you avoid redundant work?
- Hint 3
Only start counting a sequence from its smallest element -- check if (num - 1) exists in the set. If it does, this number is not the start of a sequence.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.