9.Longest Consecutive Sequence

MediumBlind 75Arrays & Hashing · 9/9

Problem

Given an unsorted array of integers nums, return the length of the longest run of consecutive values (like 1, 2, 3, 4) that can be formed from its elements. The values do not need to be adjacent in the array — only their values matter.

You must write an algorithm that runs in O(n) time.

Examples

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

Input:  nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: 0 through 8 are all present (the duplicate 0 does not extend the run).

Input:  nums = []
Output: 0

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

💡 Key Insight

Put all values in a HashSet for O(1) membership tests. A value x is the start of a run only if x - 1 is not in the set. Only from those starts do we count upward (x + 1, x + 2, …). Each value is then counted as part of exactly one upward walk, so the total work is O(n) even though there is a nested loop.

Brute Force

TimeO(n³)SpaceO(1)

Intuition

Treat every element as a potential start, and repeatedly search the array for the next value (x + 1, x + 2, …) with a linear scan until it is missing.

Algorithm

best = 0.
For each num:
- cur = num, length = 1.
- While contains(nums, cur + 1) (a linear scan): cur++, length++.
- best = max(best, length).
Return best.

Visualization

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

start 100: 101? no              → 1
start 4:   5? no                → 1
start 1:   2 ✓ 3 ✓ 4 ✓ 5? no    → 4
start 3:   4 ✓ 5? no            → 2
best = 4

Code

java

class Solution {
    public int longestConsecutive(int[] nums) {
        int best = 0;
        for (int num : nums) {
            int cur = num;
            int length = 1;
            while (contains(nums, cur + 1)) { // O(n) scan for every step
                cur++;
                length++;
            }
            best = Math.max(best, length);
        }
        return best;
    }

    private boolean contains(int[] nums, int target) {
        for (int x : nums) {
            if (x == target) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(n³) — for each start, up to n steps, each with an O(n) scan.
Space: O(1) — no extra structures.

Sorting

TimeO(n log n)SpaceO(1) to O(log n)

Intuition

After sorting, consecutive values sit next to each other. Walk the sorted array and extend the current run when the next value is exactly one larger, skip exact duplicates, and reset otherwise.

Algorithm

If empty, return 0.
Sort nums. best = 1, cur = 1.
For i = 1..n-1:
- If nums[i] == nums[i-1], continue (duplicate, run unchanged).
- Else if nums[i] == nums[i-1] + 1, cur++.
- Else cur = 1.
- best = max(best, cur).
Return best.

Visualization

sorted: [0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
cur:     1  1  2  3  4  5  6  7  8  9   (duplicate 0 skipped)
best = 9

Code

java

import java.util.Arrays;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int best = 1;
        int cur = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                continue; // duplicates neither extend nor break the run
            }
            if (nums[i] == nums[i - 1] + 1) {
                cur++;
            } else {
                cur = 1; // gap: start a new run
            }
            best = Math.max(best, cur);
        }
        return best;
    }
}

Complexity

Time: O(n log n) — dominated by sorting.
Space: O(1) to O(log n) — sorting stack space.

Hash Set with Run StartsOptimal

TimeO(n)SpaceO(n)

Intuition

A set gives O(1) lookups, but naively counting upward from every element can still be O(n²) (e.g. from 1, then from 2, then from 3 ... of the same run). The trick: only begin counting at x when x - 1 is absent — that x is the smallest value of its run. Every other element is reached only during its run's single upward walk, so the inner loop does O(n) total work across the whole algorithm.

Algorithm

Insert all values into Set<Integer> set.
best = 0.
For each x in set:
- If set.contains(x - 1), skip — x is not a run start.
- Otherwise length = 1; while set.contains(x + length), length++.
- best = max(best, length).
Return best.

Dry Run

flowchart TD
    A["set = {100, 4, 200, 1, 3, 2}"] --> B{"x = 100: 99 in set?"}
    B -->|"no, start"| C["101 missing: length 1"]
    A --> D{"x = 4: 3 in set?"}
    D -->|"yes"| E["skip"]
    A --> F{"x = 1: 0 in set?"}
    F -->|"no, start"| G["2, 3, 4 present, 5 missing: length 4"]
    A --> H{"x = 200: 199 in set?"}
    H -->|"no, start"| I["201 missing: length 1"]
    C --> J["best = 4"]
    G --> J
    I --> J

Code

java

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

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int best = 0;
        for (int x : set) { // iterate the set, so duplicates are visited once
            if (set.contains(x - 1)) {
                continue; // x is in the middle of a run; its start will count it
            }
            int length = 1;
            while (set.contains(x + length)) {
                length++;
            }
            best = Math.max(best, length);
        }
        return best;
    }
}

Complexity

Time: O(n) — building the set is O(n); each element is touched by at most one upward walk plus one start check.
Space: O(n) — the hash set.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n³)	O(1)
Sorting	O(n log n)	O(1)–O(log n)
Hash Set with Run Starts	O(n)	O(n)

Common Pitfalls

Skipping the x - 1 check — the solution is still correct but degrades to O(n²) on a long run like [1..10^5].
Iterating over nums instead of the set: an array with many copies of a run start re-walks the run each time (e.g. [1,1,1,...,2,3,...]), which can blow up to O(n²).
In the sorting approach, resetting cur on a duplicate — [0, 0, 1, 2] must give 3, not 2.
Forgetting the empty array, which must return 0.