AlgoMaster Logo

Longest Consecutive Sequence

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to find the longest run of consecutive integers 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 constraint that drives everything here is the O(n) time requirement. Sorting gives an O(n log n) solution, but the problem asks us to do better. So the question is how to detect consecutive sequences without sorting.

Every consecutive sequence has a single starting element, the one with no predecessor (num - 1 is absent from the array). If we identify those starting points efficiently and count forward from each, we avoid recounting numbers that sit in the middle of a run.

Key Constraints:

  • 0 <= nums.length <= 10^5 → With up to 100,000 elements, an O(n^2) solution risks 10^10 operations, so the required O(n) bound rules out repeated linear scans.
  • -10^9 <= nums[i] <= 10^9 → Values span four billion, so index-based structures (counting sort, boolean arrays) would need an impractically large array. A hash-based structure is the practical choice. The values fit in a 32-bit signed integer, and num + 1 on the maximum value 10^9 stays well within int range, so no overflow guard is needed.

Approach 1: Brute Force

Intuition

For every number in the array, build the longest consecutive sequence that starts from it. For each number num, check whether num + 1 exists, then num + 2, and so on, counting until the chain breaks.

Without a fast lookup structure, each existence check scans the entire array. That is the part this approach pays for later.

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

For each element, we scan the array for consecutive successors and measure how far the chain extends.

1Start. longestStreak=0
0
100
1
4
2
200
3
1
4
3
5
2
1/8

Starting from 1, we find 2, 3, and 4, giving a streak of 4. The starts at 2 and 3 rediscover part of that same run (streaks of 3 and 2), which is the redundant work this approach repeats. The other elements each form a streak of 1, so the answer is 4.

Code

Two costs stack up here: every existence check scans the entire array, and we start a sequence from every element, including those in the middle of an existing run. The next approaches attack each cost in turn, first by ordering the data, then by replacing the linear scan with O(1) lookups.

Approach 2: Sorting

Intuition

Sorting brings consecutive numbers next to each other, so a sequence like 5, 6, 7, 8 ends up as an adjacent run. After sorting, a single pass detects every run.

Walk through the sorted array comparing each element to the one before it. If the current element is exactly one larger, extend the current streak. If it equals the previous element, it is a duplicate, so leave the streak unchanged and move on. Otherwise the run breaks and the streak resets to 1. Skipping duplicates matters because a repeated value like 1, 1, 2 would otherwise reset the streak between the two 1s and lose the count.

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). The next approach removes the sort entirely by storing the numbers in a hash set, which answers "does this neighbor exist?" in O(1).

Approach 3: Hash Set (Optimal)

Intuition

A hash set answers "does this number exist?" in O(1). Putting every number into a set replaces the O(n) array scan from the brute force with a constant-time check.

Fast lookups alone don't fix the redundant counting. Building a sequence from every number repeats work: in [1, 2, 3, 4], starting from 2 counts 2, 3, 4 (length 3), and later starting from 1 counts 1, 2, 3, 4 (length 4), recounting 2, 3, and 4.

The fix is to count only from sequence beginnings. A number begins a sequence exactly when num - 1 is not in the set. For example:

  • 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)

With this check, each number is visited at most twice: once in the outer loop, and once when counted forward from the start of its sequence. That 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