Longest Consecutive Sequence

What does it solve?

Given an unsorted array, find the length of the longest run of consecutive integers (like 1,2,3,4). Sorting would cost O(N log N); a hash set does it in O(N).

Key insight: put every number in a set for O(1) membership tests. A number is the start of a run only if num − 1 is not in the set. From each start, walk num+1, num+2, … counting the length. Because only true starts trigger a walk, every element is touched at most twice, keeping it O(N).

The core idea

// only walk from a run's start
s = set(nums); best = 0
for x in s:
  if (x − 1) not in s: # x starts a run
    len = 1
    while (x + len) in s: len++
    best = max(best, len)

Complexity

Time complexity

O(N)

The "start only" guard means each number is walked through at most once across all runs. No sorting needed.

Space complexity

O(N)

The hash set stores every distinct value. Duplicates collapse automatically, which also removes double counting.

Examples & edge cases

Live animation — walk runs only from their true start

candidate x / run start walking the run probing x+len skipped (not a start) longest run found

Hash set of distinct values

Current run on the number line

—

Current step detail

x = — run len = — probing = — best = —

Step — of —

candidate x

—

from the set

current run

—

length so far

starts walked

—

true run heads

longest run

—

best length

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	x	x−1 in set?	Role	run length	Action	best

C++ implementation

longest_consecutive.cpp

#include <bits/stdc++.h>
using namespace std;

// Length of the longest run of consecutive integers
int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;

    for (int x : s) {
        // only start counting from the beginning of a run
        if (!s.count(x - 1)) {
            int cur = x, len = 1;
            while (s.count(cur + 1)) {
                cur++;
                len++;
            }
            best = max(best, len);
        }
    }
    return best;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << longestConsecutive(nums) << "\n"; // 4  (1,2,3,4)
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars