Longest Consecutive Sequence — Why sorting is a trap

Assume an array [100, 4, 200, 3, 1, 2]

You are supposed to find the length of longest sequence, it need not be contiguous. Here the longest sequence is [1,2,3,4] length = 4

Whenever we come across such question, we first think of sorting the array then finding the sequence, but this question can be solved with O(n) time complexity!

The trick here is using HashSet!

A HashSet stores only unique elements and provides O(1) average-time lookup, insertion, and deletion. Elements are arranged in any order so there is no indexing.

How to solve this problem using HashSet?

1. Traverse through the array and insert elements into the HashSet.
2. Traverse the HashSet and check if the a predecessor exist for an element. If predecessor exist, then move to the next element. If it doesn’t exist, then this number is the start of the sequence.
3. When the start is found, check for the next elements and append the count.
4. Take the length which is maximum or longest.

Dry Run

Example : [200, 4, 100, 3, 1, 2]

First include all elements in the HashSet

Element = 200

Does 200–1 = 199 present in the set? No, max length = 1

Search for the next elements in the sequence: 200+1 = 201 is it present in the set? No, move to the next element

Element = 4

Does 4–1 = 3 present in the set? Yes, Move to next element

Element = 100

Does 100–1 = 99 present in the set? No, max length=1

Search for the next elements in the sequence: 100+1 = 101 is it present in the set? No, move to the next element

Element = 3

Does 3–1 = 2 present in the set? Yes, move to next element

Element = 1

Does 1–1 = 0 present in the set? No, max length = 1

Search for the next element in the sequence:

1+1 = 2 is it present in the set? Yes, max length = 2

2+1 = 3 is it present in the set? Yes, max length = 3

3+1 = 4 is it present in the set? Yes, max length = 4

4+1 = 5 is it present in the set? No, move to next element

Element = 2

Does 2–1 = 1 present in the set? Yes, end of traversal

Max Length = 4

Complexity

Time Complexity = O(n)

Space Complexity = O(n)

Each element can become part of a sequence only once, and HashSet lookups take O(1) on average. Therefore, the overall time complexity is O(n).

Final Takeaway

The natural instinct for sequence-related problems is to sort the array and then look for consecutive numbers. While that works, it costs O(n log n) time.

The HashSet approach avoids sorting completely. By identifying only the starting points of sequences and expanding from there, we can solve the problem in O(n) time.

Whenever a problem asks for:

• Longest consecutive sequence
• Fast existence checks
• O(n) time complexity

consider using a HashSet before reaching for sorting.