Topics › Arrays › Medium

Longest Consecutive Sequence in an Array

Medium TUF ID 563 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an unsorted array of integers nums. Find the length of the longest sequence of consecutive integers x, x + 1, x + 2, ..., x + L - 1 such that every value of the sequence appears somewhere in the array. Positions do not matter: the values can be scattered in any order. Repeated values count once. Return 0 for an empty array.

Constraints: 0 ≤ n ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9. The LeetCode version asks for an O(n) solution.

Example 1

nums = [100, 4, 200, 1, 3, 2]
answer = 4          // 1, 2, 3, 4 are all present

Example 2

nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
answer = 9          // 0 through 8; the second 0 changes nothing

Example 3

nums = [1, 2, 0, 1]
answer = 3          // 0, 1, 2; duplicates neither extend nor break the run

Note the difference from “longest increasing subarray”: here we compare values, not neighbours in the array.

Approach 1: Brute force

Intuition. Every consecutive run starts at some value that is in the array. So try each array value x as a starting point and keep asking “is x + 1 in the array? is x + 2?” until the answer is no. The longest walk found is the answer. Without any extra data structure, each question is a linear search through the array.

Trying non-starting values (like 3 in example 1) is wasted work but harmless: their walks are shorter than the walk from the true start, which is also tried.

Algorithm.

1. For each value x in nums: set cur = x, len = 1.
2. While cur + 1 is found by a linear search, do cur++ and len++.
3. Track the maximum len; return it (0 if the array is empty).

static int bruteForce(int[] nums) {
    int best = 0;
    for (int x : nums) {
        int cur = x, len = 1;
        while (cur != Integer.MAX_VALUE && linearSearch(nums, cur + 1)) {
            cur++;
            len++;
        }
        best = Math.max(best, len);
    }
    return best;
}

static boolean linearSearch(int[] nums, int target) {
    for (int v : nums) if (v == target) return true;
    return false;
}

Complexity. Time O(n^3) in the worst case: for the array 0, 1, ..., n - 1, the walk from value x takes n - x steps and each step is an O(n) search, which sums to about n^3 / 2. Space O(1).

The test cur != Integer.MAX_VALUE stops cur + 1 from wrapping around to Integer.MIN_VALUE, which would otherwise make MAX_VALUE and MIN_VALUE look consecutive.

Approach 2: Better, sort and scan

Intuition. Once the values are sorted, every consecutive run sits in one contiguous block, possibly with duplicates mixed in. A single left-to-right pass can then measure runs by comparing each element with the previous one:

• equal to the previous value: a duplicate, skip it without touching the run;
• exactly one more: the run grows;
• anything else: a gap, so a new run of length 1 begins.

We sort a copy so the caller’s array is not reordered behind their back.

Algorithm.

1. If the array is empty, return 0.
2. Sort a copy a. Set best = 1, len = 1.
3. For i from 1 to n - 1: skip if a[i] == a[i - 1]; if a[i] - a[i - 1] == 1 do len++, else set len = 1. Update best.
4. Return best.

static int better(int[] nums) {
    if (nums.length == 0) return 0;
    int[] a = nums.clone();                          // do not reorder the caller's array
    Arrays.sort(a);
    int best = 1, len = 1;
    for (int i = 1; i < a.length; i++) {
        if (a[i] == a[i - 1]) continue;              // duplicate: neither extends nor breaks the run
        if (a[i] - a[i - 1] == 1) len++;
        else len = 1;
        best = Math.max(best, len);
    }
    return best;
}

Complexity. Time O(n log n) for the sort; the scan is O(n). Space O(n) for the copy. If modifying the input is allowed, sort in place and the extra space drops to the sort’s own overhead.

Is a[i] - a[i - 1] safe from overflow? Because the array is sorted, the true difference lies in [0, 2^32 - 1], and the only such value that wraps to exactly 1 is 1 itself. So the comparison is exact even for extreme values.

This is a fine answer when O(n log n) is acceptable, but the problem explicitly asks for linear time.

Approach 3: Optimal, hash set with “start of run” detection

Intuition. The brute force was slow for two reasons: each membership question cost O(n), and runs were walked many times, once from each of their members. A hash set fixes the first problem, giving O(1) average membership tests. The second fix is the clever part.

A value x is the start of its run exactly when x - 1 is not present. If we only begin walking from starts, every run is walked once, from its smallest element, and every value is visited by exactly one walk: the walk of the run it belongs to. Values that are not starts cost a single contains check and are skipped. So the total work over all walks is O(n), even though there is a while loop inside a for loop.

We iterate over the set, not the original array. If the array contained the start value many times, iterating the array would walk the same run once per copy, and an input made of 50,000 copies of 1 followed by 2, 3, ..., 50000 would take about 2.5 × 10^9 steps.

Algorithm.

1. Insert every value into a HashSet.
2. For each x in the set: if x - 1 is in the set, skip x.
3. Otherwise walk upward from x while cur + 1 is in the set, counting the length.
4. Track and return the maximum length.

static int optimal(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int best = 0;
    for (int x : set) {                              // iterate the set, so duplicates are visited once
        if (x != Integer.MIN_VALUE && set.contains(x - 1)) continue;   // x - 1 exists: x is not a start
        int cur = x, len = 1;
        while (cur != Integer.MAX_VALUE && set.contains(cur + 1)) {
            cur++;
            len++;
        }
        best = Math.max(best, len);
    }
    return best;
}

Dry run on nums = [100, 4, 200, 1, 3, 2], set {1, 2, 3, 4, 100, 200} (a HashSet may iterate in any order; the result does not depend on it):

The values 2, 3, 4 are examined twice in total: once as skipped candidates and once inside the walk from 1. That “constant number of touches per value” is the heart of the O(n) bound.

Complexity. Time O(n) on average: building the set is n insertions, the outer loop does at most n start checks, and all walks together take at most n steps. Space O(n) for the set.

The guards x != Integer.MIN_VALUE and cur != Integer.MAX_VALUE prevent x - 1 and cur + 1 from wrapping around. They are unnecessary under LeetCode’s ±10^9 bounds, but they cost nothing and keep the method correct for every int.

Edge cases and pitfalls

• Empty array. The answer is 0. The sorting approach returns early; the others never enter their loops.
• Duplicates. [1, 2, 0, 1] has answer 3. In the sorted scan, a duplicate must be skipped rather than treated as a gap, or the run would reset. In the hash set approach duplicates disappear automatically.
• All equal values. [7, 7, 7] gives 1, not 3.
• Iterate the set, not the array. Otherwise repeated start values re-walk the same run and the linear bound is lost.
• Negative numbers. Nothing special: [-3, 10, -1, 1, -2, 0] has the run -3..1 of length 5.
• Integer overflow at the extremes. [Integer.MAX_VALUE, Integer.MIN_VALUE] must give 1. Naive x + 1 turns MAX_VALUE into MIN_VALUE and reports a run of 2.
• Do not mutate the input. The sorting approach works on a clone; the tests confirm the original array is unchanged.

Related problems

• Longest Consecutive Sequence in an Array is the same problem as it appears in the A2Z array track.
• Two Sum uses the same “is the value I need already in a hash structure?” question.
• Largest Subarray with K sum is the next hashing problem in this part of the SDE sheet.
• Longest Substring Without Repeating Characters also maintains a set to find the longest valid stretch.
• Basic Hashing covers the hash set and hash map fundamentals used here.