Topics › Arrays › Medium

Longest Consecutive Sequence in an Array

Medium TUF ID 2835 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an unsorted array of integers nums, return the length of the longest run of consecutive integers that are all present in the array. The elements of the run do not have to be adjacent in the array, only consecutive in value: [100, 4, 200, 1, 3, 2] contains the run 1, 2, 3, 4, so the answer is 4. Duplicates may appear and count only once. The follow-up asks for O(n) time.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer, negatives allowed.

Example 1

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

Example 2

nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
answer = 9               // 0, 1, 2, ..., 8; the duplicate 0 does not help or hurt

Example 3

nums = []
answer = 0               // nothing present, nothing consecutive

Approach 1: Brute force

Intuition. Pick any element x and ask “is x + 1 in the array? is x + 2?” and keep going until a value is missing. Each question is a linear search. Doing this from every element finds every run, including the longest one, because the longest run starts somewhere and we try every starting point. Nothing is pre-processed, so correctness is obvious, but every lookup costs a full scan.

Algorithm.

1. For each element x: set len = 1 and next = x + 1.
2. While next is found by a linear search of the array: len++, next++.
3. Keep the maximum len seen.

static int bruteForce(int[] nums) {
    int longest = 0;
    for (int x : nums) {
        int len = 1;
        long next = (long) x + 1;                // long: x + 1 overflows int for Integer.MAX_VALUE
        while (contains(nums, next)) {
            len++;
            next++;
        }
        longest = Math.max(longest, len);
    }
    return longest;
}

private static boolean contains(int[] nums, long value) {
    for (int v : nums) if (v == value) return true;
    return false;
}

Complexity. Time O(n^2) in the common case (each element triggers at least one O(n) search) and up to O(n^3) when the whole array is one long run, because every start point walks almost the entire run with a linear search per step. Space O(1).

next is a long on purpose. If x is Integer.MAX_VALUE, then x + 1 as an int wraps to Integer.MIN_VALUE, and if that value happens to be in the array the run would be extended incorrectly. In the long domain 2147483648 is simply not in the array.

Approach 2: Better, sort and scan

Intuition. Consecutive values are adjacent in sorted order. After sorting, a run is a maximal stretch where each element is exactly one more than the previous. Duplicates are also adjacent after sorting, so they are easy to skip: an element equal to its predecessor neither extends the current run nor breaks it. One linear scan then finds the longest run.

Algorithm.

1. If the array is empty return 0. Sort (a copy, to leave the input unchanged).
2. Set longest = 1, len = 1.
3. For i from 1: if a[i] == a[i-1] skip; else if a[i] - a[i-1] == 1 then len++, otherwise len = 1. Update longest.

static int better(int[] nums) {
    if (nums.length == 0) return 0;
    int[] a = nums.clone();
    Arrays.sort(a);
    int longest = 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 ((long) a[i] - a[i - 1] == 1) len++;  // long: the difference can overflow int
        else len = 1;
        longest = Math.max(longest, len);
    }
    return longest;
}

Complexity. Time O(n log n) for the sort; the scan is O(n). Space O(n) for the copy, or O(1) extra if sorting in place is acceptable.

The long cast in the difference is about honesty more than necessity. In sorted order a[i] >= a[i-1], so the true difference is between 0 and 2^32 - 1; when it overflows int the wrapped result is negative (Integer.MAX_VALUE - Integer.MIN_VALUE wraps to -1) and can never be mistaken for 1. Still, reasoning about which overflows happen to be harmless is exactly the kind of thing that goes wrong under interview pressure. Doing the subtraction in long costs nothing and removes the guesswork.

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

Intuition. A hash set makes “is value v present?” an O(1) question, which already turns the brute force into something much faster. But if we start walking from every element, a run of length L is walked from each of its L elements, costing O(L^2) in total. The fix is to walk a run only from its smallest element, which is easy to recognise: x is the start of a run exactly when x - 1 is not in the set. Every other element of the run is skipped in O(1). Each run is then walked exactly once, so the total work over all runs is proportional to the number of distinct elements.

Algorithm.

1. Insert all elements into a HashSet (this also removes duplicates).
2. For each x in the set: if x - 1 is in the set, skip it.
3. Otherwise walk x, x + 1, x + 2, ... while each value is present, counting the length.
4. Return the maximum length.

static int optimal(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int longest = 0;
    for (int x : set) {
        if (x != Integer.MIN_VALUE && set.contains(x - 1)) continue;   // not the start of a run
        int cur = x, len = 1;
        while (cur != Integer.MAX_VALUE && set.contains(cur + 1)) {
            cur++;
            len++;
        }
        longest = Math.max(longest, len);
    }
    return longest;
}

Dry run on nums = [100, 4, 200, 1, 3, 2] (set iteration order is arbitrary; assume 1, 2, 3, 4, 100, 200):

Answer 4.

Complexity. Time O(n) on average: building the set is O(n), the outer loop visits each distinct element once, and the inner while steps are charged to the run they belong to, with each run walked exactly once, so all inner steps together are at most n. Space O(n) for the set.

The two guards against Integer.MIN_VALUE and Integer.MAX_VALUE keep the integer arithmetic honest. Without them, x - 1 for MIN_VALUE wraps to MAX_VALUE, so an array containing both would treat MIN_VALUE as “not a start”, and cur + 1 for MAX_VALUE wraps to MIN_VALUE, making the walk continue around the integer circle. The test [MAX_VALUE, MIN_VALUE] -> 1 checks exactly this.

Edge cases and pitfalls

• Empty array. Return 0, not 1. The sorted approach has an explicit check; the other two return 0 because their loops never run.
• Duplicates. [1, 1, 1] has a longest run of 1. The set version de-duplicates for free; the sorted version must skip equal neighbours or it resets len incorrectly.
• Negative numbers and zero. [-2, -1, 0, 1, -5] gives 4. Nothing special is needed, consecutive is consecutive.
• Overflow at the ends of the int range. Covered above; use long for x + 1 and for differences, or guard against MIN_VALUE and MAX_VALUE explicitly.
• Walking from every element in the hash-set version. This is the classic mistake that turns the O(n) solution into O(n^2) on an input like [1, 2, 3, ..., n]. Always check x - 1 first.
• Iterating the array instead of the set. With many duplicates, iterating nums would re-check the same start many times. Iterating the set keeps the work proportional to the distinct count.

Related problems

• Two Sum is the simplest example of trading a hash lookup for a linear scan.
• Count subarrays with given sum is another problem where a hash map replaces an inner loop entirely.
• Majority Element-II also compares a hash-map solution with a constant-space alternative.