How do you approach Longest Consecutive Sequence?

Put all numbers in a hash set for O(1) lookups.

What is the time complexity of Longest Consecutive Sequence?

Time complexity: O(n) - each number is visited at most twice. Space complexity: O(n) for the set.

What are common mistakes on Longest Consecutive Sequence?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

gitGood.dev

← Back to problems

Longest Consecutive Sequence

MediumAlgorithms

Description

Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

Example 1

Input: nums = [100,4,200,1,3,2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]

Output: 9

Constraints

- 0 <= nums.length <= 10^5 - -10^9 <= nums[i] <= 10^9

Longest Consecutive Sequence: approach, complexity and pitfalls

A medium arrays & hashing problem, graded against 7 test cases (4 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashingproblems →

If you are stuck

Show the 3-step hint ladder

Put all numbers in a hash set for O(1) lookups.
A number is the start of a sequence if (num - 1) is not in the set.
For each sequence start, count consecutive numbers going up.

The optimal approach

Show the approach: Hash Set

Add all numbers to a set. For each number, check if it's the start of a sequence (num - 1 not in set). If so, count consecutive numbers from that start. Track the maximum length.

Time: O(n) - each number is visited at most twice
Space: O(n) for the set

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.