Problem statement

Given an unsorted array nums, return the length of the longest run of consecutive integers (the elements can appear anywhere in the array).

Your algorithm should run in O(n) time.

Example 1

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest run is [1,2,3,4].

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints

• 0 <= nums.length <= 30
• -1000 <= nums[i] <= 1000

Hints for Longest Consecutive Sequence

1. Hint 1

   Put everything in a set for O(1) membership checks.

2. Hint 2

   Only start counting from numbers that begin a run (x-1 is absent).

How to solve Longest Consecutive Sequence

Sorting would cost O(n log n). Instead put every value into a set and only start counting from a value that begins a run — one whose predecessor is absent. From each such start, walk upward while the next value exists.

Approach

1. Record membership of every value (a hash set, or a direct-address table when the value range is small).
2. For each distinct value v, check whether v - 1 is present.
3. If it is, v is in the middle of a run — skip it.
4. Otherwise v starts a run: count v, v+1, v+2, … while each is present.
5. Keep the longest length seen.

Why it works

Restricting the walk to run starts is what keeps this linear. Each run is traversed exactly once — from its unique smallest element — so the total work across all runs is bounded by the number of distinct values, even though the code contains a nested loop. Without that check, a long run would be re-walked from every one of its members, degrading to quadratic.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The v - 1 check is not an optimisation but the reason the complexity holds; dropping it makes the algorithm quadratic.
• An empty array must return 0.
• Duplicates must not inflate the count — membership, not multiplicity, is what matters.
• Values can be negative, so a direct-address table needs an offset.

Reference solution

Python

from typing import List

def longestConsecutive(nums: List[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best

Java

public static int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;
    final int OFFSET = 1000, SIZE = 2001;
    boolean[] present = new boolean[SIZE];
    for (int x : nums) present[x + OFFSET] = true;
    int best = 0;
    for (int v = 0; v < SIZE; v++) {
        if (!present[v]) continue;
        if (v > 0 && present[v - 1]) continue;
        int len = 1;
        while (v + len < SIZE && present[v + len]) len++;
        if (len > best) best = len;
    }
    return best;
}

C++

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    const int OFFSET = 1000, SIZE = 2001;
    vector<bool> present(SIZE, false);
    for (int x : nums) present[x + OFFSET] = true;
    int best = 0;
    for (int v = 0; v < SIZE; v++) {
        if (!present[v]) continue;
        if (v > 0 && present[v - 1]) continue;
        int len = 1;
        while (v + len < SIZE && present[v + len]) len++;
        if (len > best) best = len;
    }
    return best;
}

JavaScript

var longestConsecutive = function(nums) {
    const s = new Set(nums);
    let best = 0;
    for (const x of s) {
        if (!s.has(x - 1)) {
            let len = 1;
            while (s.has(x + len)) len++;
            best = Math.max(best, len);
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium