AlgoMaster Logo

Longest Consecutive Sequence

Last Updated: April 6, 2026

medium
4 min read

Understanding the Problem

We need to find the longest streak of consecutive integers hiding inside an unsorted array. The numbers don't have to be adjacent in the array, they just need to form a sequence like 5, 6, 7, 8 somewhere in the collection.

The tricky part is the O(n) time requirement. Sorting would give us an easy O(n log n) solution, but the problem explicitly asks us to do better. So the question becomes: how do we detect consecutive sequences without sorting?

The key observation is that every consecutive sequence has a "start" element, one that has no predecessor (i.e., num - 1 doesn't exist in the array). If we can identify these starting points efficiently, we only need to count forward from each one.

Key Constraints:

  • 0 <= nums.length <= 10^5 → With up to 100,000 elements, O(n^2) might barely pass but O(n) is required by the problem statement.
  • -10^9 <= nums[i] <= 10^9 → The value range is huge, so index-based approaches (like counting sort or boolean arrays) are out. We need a hash-based structure.

Approach 1: Brute Force

Intuition

The most straightforward idea: for every number in the array, try to build the longest consecutive sequence starting from it. For each number num, check if num + 1 exists, then num + 2, and so on. Keep counting until the chain breaks.

To check whether a number exists, the simplest way is to scan the entire array each time. It's not efficient, but it gets the job done.

Algorithm

  1. Initialize longestStreak to 0.
  2. For each number num in the array:
    1. Set currentNum = num and currentStreak = 1.
    2. While currentNum + 1 exists somewhere in the array, increment currentNum and currentStreak.
    3. Update longestStreak if currentStreak is larger.
  3. Return longestStreak.

Example Walkthrough

0
100
1
4
2
200
3
1
4
3
5
2
nums

For each element, we scan the entire array for consecutive successors. Starting from 1, we find 2, 3, and 4 in the array, giving us a streak of 4. Starting from any other element yields a shorter streak.

Code

Every existence check scans the entire array, and we start a sequence from every element, including those in the middle of a sequence. What if we could check existence in O(1) and avoid redundant starting points?

Approach 2: Sorting

Intuition

Sorting is a natural way to bring consecutive numbers next to each other. Once the array is sorted, consecutive sequences become adjacent runs that we can detect in a single pass.

After sorting, we just walk through the array. If the current element is exactly one more than the previous, we extend our current streak. If it's the same (a duplicate), we skip it. Otherwise, the streak breaks and we start fresh.

Algorithm

  1. If the array is empty, return 0.
  2. Sort the array.
  3. Initialize longestStreak = 1 and currentStreak = 1.
  4. Iterate from index 1 to n - 1:
    1. If nums[i] == nums[i-1] + 1, increment currentStreak.
    2. Else if nums[i] != nums[i-1] (skip duplicates), reset currentStreak = 1.
    3. Update longestStreak if currentStreak is larger.
  5. Return longestStreak.

Example Walkthrough

1Sorted array. Initialize: currentStreak=1, longestStreak=1
0
1
1
2
2
3
3
4
4
100
5
200
1/7

Code

Sorting takes O(n log n), but the problem requires O(n). Can we detect consecutive sequences without sorting, using only O(1) lookups to check if a number's neighbor exists?

Approach 3: Hash Set (Optimal)

Intuition

Here's the key insight: a hash set gives us O(1) lookups. If we dump all numbers into a set, we can instantly check whether any given number exists.

But that alone isn't enough. If we try to build a sequence starting from every number, we'd still do redundant work. Think about the sequence [1, 2, 3, 4]. If we start counting from 2, we find 2, 3, 4 (length 3). Then when we reach 1, we count 1, 2, 3, 4 (length 4). We counted 2, 3, and 4 multiple times.

The trick is to only start counting from sequence beginnings. A number is the start of a sequence if and only if num - 1 is NOT in the set. This means:

  • 1 starts a sequence (because 0 isn't present)
  • 2 does NOT start a sequence (because 1 is present)
  • 100 starts a sequence (because 99 isn't present)

By only starting from sequence beginnings, each number gets visited at most twice: once in the outer loop and once when being counted forward from a start. This keeps the total work at O(n).

Algorithm

  1. Insert all numbers into a hash set.
  2. Initialize longestStreak = 0.
  3. For each number num in the set:
    1. If num - 1 is NOT in the set, this is the start of a sequence.
    2. Count forward: check num + 1, num + 2, etc., incrementing a counter.
    3. Update longestStreak with the counter.
  4. Return longestStreak.

Example Walkthrough

nums
1Build hash set from all elements
0
100
1
4
2
200
3
1
4
3
5
2
numSet
1Set contains all unique elements
1
2
3
4
100
200
1/7

Code