# Longest Consecutive Sequence

> How to solve Longest Consecutive Sequence: find the longest run of consecutive integers in an unsorted array in linear time with a hash set.

- Difficulty: Medium
- Category: Arrays & Hashing
- Topics: Array, Hash Table, Union Find
- Published 2026-08-21

## Problem

You are given an unsorted array of integers. Find the length of the longest run of consecutive integers that appear somewhere in the array; the values need not be adjacent in the array itself, only present as a set.

**Example.** For `[100, 4, 200, 1, 3, 2]`, the values `1, 2, 3, 4` are all present, forming a run of length `4`, which is the answer.

## Key idea

Sorting the array first makes consecutive runs sit next to each other, so a single scan afterward finds the longest run in O(n log n) total. That works, but it is not the fastest option.

To do better, drop every value into a hash set so membership can be checked in O(1). The key trick is to only start counting a run from a number that is genuinely the start of one, meaning `number - 1` is not in the set. For each such starting number, walk upward, checking whether `number + 1`, `number + 2`, and so on are present, and track how far the run extends. Numbers in the middle of a run are skipped as starting points rather than re-explored. Because every number is walked at most once, as part of the single run it belongs to, the total work across every start adds up to O(n) despite the nested-loop appearance.

## Solution

```typescript
function longestConsecutive(nums: number[]): number {
  const values = new Set(nums);
  let longest = 0;

  for (const num of values) {
    if (values.has(num - 1)) {
      continue; // not the start of a run, it will be counted from its actual start
    }

    let length = 1;
    let current = num;
    while (values.has(current + 1)) { // extend the run while it stays consecutive
      current++;
      length++;
    }

    longest = Math.max(longest, length);
  }

  return longest;
}
```

## Complexity

- **Time:** O(n). The set build is O(n), and every number is visited a bounded number of times across all run walks combined.
- **Space:** O(n). The hash set holds every distinct value.

## Watch out for

- Skipping the "is this a start" check turns the algorithm back into O(n²), since interior numbers would redundantly re-walk runs they already belong to.
- Duplicate values do not extend a run and should not be double-counted; a set naturally collapses them.
- An empty array should return `0` rather than assuming at least one element exists.

## Pattern

This is hash-set membership combined with "only extend from a boundary." A union-find structure can solve the same grouping problem, but walking from detected starts is the simpler idiomatic fit here, and the same space-for-speed trade recurs anywhere a full rescan needs to be avoided.

---

Canonical URL: https://www.marauderbot.com/questions/longest-consecutive-sequence
