Longest Consecutive Sequence

1. Define the problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence (numbers that would be consecutive if sorted, like 3, 4, 5, 6) that can be built using values from the array. You must write an algorithm that runs in O(n) time. Sorting first would already break the O(n) requirement. Instead, drop every value into a hash set for instant membership checks. The key insight: only bother starting a sequence count from a number whose predecessor (value - 1) is not in the set — that guarantees each number is only ever the start of exactly one count, so every number in the array is visited a small, bounded number of times overall. From each valid start, keep checking value + 1, value + 2, ... in the set until the chain breaks, and track the longest chain seen.

Constraints

0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums_i ≤ 10⁹

Example

Inputnums = [100, 4, 200, 1, 3, 2]

Output4

Explanation The longest consecutive sequence is [1, 2, 3, 4], which has length 4.

2. Know the words first

In plain terms

Hash set: A collection that lets you ask "is this value in here?" in roughly constant time, regardless of how many values it holds.

3. Visualize the solution

Only grow chains that start at a true beginning

0100

2200

Statuscheck-start

nums[0]=100. Is 99 in the set? No — 100 is a true start. Chain of just {100}: length 1. best=1.

What happens in this step

value = 100, predecessor 99 in set? no -> true start
current = 100, length = 1
101 in set? no -> chain stops

best = 1

Step 1 of 5

Steps to visualize

Put every value into a set for fast lookups.
For each value, check whether value - 1 is in the set — if it is, skip it, since some other value will count this chain.
If value - 1 is not in the set, this value is a true chain start: count forward through value + 1, value + 2, ... while each is present.
Track the longest chain length found across all true starts.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Only grow chains that start at a true beginning

0100

2200

Statuscheck-start

nums[0]=100. Is 99 in the set? No — 100 is a true start. Chain of just {100}: length 1. best=1.

What happens in this step

value = 100, predecessor 99 in set? no -> true start
current = 100, length = 1
101 in set? no -> chain stops

best = 1

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;

  for (const num of set) {
    if (!set.has(num - 1)) {
      let length = 1;
      let current = num;
      while (set.has(current + 1)) {
        current++;
        length++;
      }
      best = Math.max(best, length);
    }
  }

  return best;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [100, 4, 200, 1, 3, 2]`	`4`	example from the docstring
`nums = []`	`0`	smallest valid input: an empty array
`nums = [7]`	`1`	a single element is its own chain of length 1
`nums = [1, 2, 2, 3]`	`3`	duplicate values must not inflate the chain length
`nums = [-1, -2, -3, 0, 1]`	`5`	a chain that spans negative and positive values
`nums = [10, 20, 30]`	`1`	no two values are consecutive, so the longest chain is length 1

Longest Consecutive Sequence