Back to solutions

Longest Consecutive Sequence

MediumArrays

Find the longest run of consecutive integers, in O(n).

Open problem
Constraints
  • 0 <= n <= 10^5
  • -10^9 <= nums[i] <= 10^9

Hash set, start of run only

Time O(n)Space O(n)

Put all numbers in a set. A number x begins a run only if x-1 is absent. From each such start, walk upward (x+1, x+2, ...) counting while values exist. Because every number is the start of at most one run, the total work is O(n).

Key terms
run start:
A value with no predecessor in the set, so counting begins there.
amortised O(n):
Each value is visited a constant number of times overall despite the inner loop.
int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int x : s) {
        if (!s.count(x - 1)) {
            int len = 1, cur = x;
            while (s.count(cur + 1)) { cur++; len++; }
            best = max(best, len);
        }
    }
    return best;
}
Step by step
  1. Insert all values into a hash set (drops duplicates).
  2. For each value x, only proceed if x-1 is not in the set (x starts a run).
  3. Count upward while x+1, x+2, ... are present.
  4. Track the longest run length and return it.