Longest Consecutive Sequence

Problem

Given an unsorted array of integers, return the length of the longest run of consecutive integers — the values must form a k, k+1, k+2, … run, but they may appear in any order in the array. Aim for O(n).

Constraints

• 0 ≤ nums.length ≤ 10⁵
• −10⁹ ≤ nums[i] ≤ 10⁹

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def longestConsecutive(self, nums):
        s = set(nums)
        best = 0
        for x in s:
            if x - 1 not in s:
                y = x
                while y + 1 in s:
                    y += 1
                best = max(best, y - x + 1)
        return best

Java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int best = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) {
                int cur = n, run = 1;
                while (set.contains(cur + 1)) { cur++; run++; }
                best = Math.max(best, run);
            }
        }
        return best;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.