Longest Consecutive Sequence Solution

Problem

Given an unsorted array of integers, find the length of the longest run of consecutive integers present in it. The numbers can appear in any order, and you must solve it in O(n) time.

Example:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The numbers 1, 2, 3, 4 are all present and form the longest consecutive chain.

Counter-example: [4, 6, 8] → output 1, since no two of those numbers differ by exactly 1.

Intuition

Think of the numbers as beads that snap together when they differ by 1 — the problem asks for the longest chain of snapped beads. If we store all numbers in a hash set for O(1) lookup, we can check whether any neighbor exists instantly. The key insight is to only start building a chain from the smallest number in that chain — a number is a chain start if and only if its predecessor (num - 1) is absent from the set. This prevents counting the same chain multiple times and gives O(n) total work.

Approach 1 — Sort

Sort the array and scan it once. Whenever the next number is exactly 1 greater than the previous, extend the current streak. Skip duplicates. Reset on a gap.

Steps:

Return 0 immediately on an empty array
Sort the array in ascending order
Walk through with a running current_streak (starts at 1) and a max_streak
If the current number equals the previous number plus 1, extend current_streak
If the current number equals the previous number exactly, it's a duplicate — skip without resetting
Otherwise a gap was found — reset current_streak to 1

1def longestConsecutive(nums):
2    if not nums:
3        return 0
4
5    nums.sort()
6    max_streak = 1
7    current_streak = 1
8
9    for i in range(1, len(nums)):
10        if nums[i] == nums[i - 1] + 1:
11            current_streak += 1
12            max_streak = max(max_streak, current_streak)
13        elif nums[i] != nums[i - 1]:  # equal means duplicate, not a gap
14            current_streak = 1
15
16    return max_streak

Time: O(n log n) — dominated by sorting
Space: O(1) — no extra data structures beyond the sort's internal stack (O(log n) in practice)

Approach 2 — Hash Set (Optimal)

Load all numbers into a hash set. For each number that is a chain start (has no predecessor in the set), walk forward through the chain until it ends. Track the maximum chain length seen.

Steps:

Insert every number into a hash set for O(1) membership tests
Initialize max_streak = 0
For each number in the set, skip it if num - 1 is present (it belongs to a longer chain starting earlier)
For numbers that ARE chain starts, extend: increment current_num while current_num + 1 is in the set
Update max_streak once each chain is fully counted
Return max_streak

1def longestConsecutive(nums):
2    num_set = set(nums)
3    max_streak = 0
4
5    for num in num_set:
6        if num - 1 not in num_set:  # num is the start of a new chain
7            current_num = num
8            current_streak = 1
9
10            while current_num + 1 in num_set:
11                current_num += 1
12                current_streak += 1
13
14            max_streak = max(max_streak, current_streak)
15
16    return max_streak

Time: O(n) — each number is inserted once and extended through at most once across all chain walks
Space: O(n) — the hash set holds every unique number

Complexity Summary

Approach	Time	Space	When to use
Sort	O(n log n)	O(1)	When extra memory is prohibited or the input is nearly sorted
Hash Set	O(n)	O(n)	The standard answer when O(n) time is required by the problem

Common Mistakes

Not skipping duplicates in the sort approach: If nums[i] == nums[i-1], resetting current_streak to 1 would give the wrong answer for inputs like [1, 1, 2]. The check for equality must be explicit.
Iterating the original array instead of the set in Approach 2: Correctness is unaffected, but if the array has many duplicates every duplicate triggers its own num - 1 check, adding wasted work (though still O(n) overall). Iterating the set is cleaner.
Forgetting the chain-start guard: Without the num - 1 not in numSet check, every element would start a chain walk, making the worst-case O(n²) — e.g., for [1, 2, 3, …, n] each element walks to the end.
Off-by-one on streak initialization: Initializing current_streak = 0 before the while loop and incrementing inside causes the start element itself not to be counted, producing an answer that is 1 too low for every chain.
Returning 0 for a single-element array: max_streak starts at 0 and updates only inside the chain walk loop. For [42], the chain walk finds no neighbors so the update still executes as max(0, 1) = 1. The logic is correct as long as current_streak is initialized to 1 before the while loop.

Longest Consecutive Sequence — Solution