Longest Consecutive Sequence

Given an unsorted array of integers, return the length of the longest sequence of consecutive integers (x, x + 1, x + 2, ...) whose values all appear in the array. The values can be in any positions. The solution should run in O(n).

LeetCode: 128. Longest Consecutive Sequence

Example

Text

Input:  [10, 4, 20, 1, 2, 8, 9, 3, 19]    Output: 4   (1, 2, 3, 4)
Input:  [0, -2, 3, -1, 2, 1]              Output: 6   (-2 through 3)

Brute force: sort and count runs

After sorting, consecutive values are next to each other. Count the length of each run, skipping duplicates, which neither extend nor break a run. The comparison uses long so that sorted[i - 1] + 1 cannot wrap around when the value is Integer.MAX_VALUE.

Java

import java.util.Arrays;

public class Main {
    static int longestConsecutive(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int best = 0, run = 0;
        for (int i = 0; i < sorted.length; i++) {
            if (i > 0 && sorted[i] == sorted[i - 1]) continue;      // a duplicate changes nothing
            if (i > 0 && (long) sorted[i - 1] + 1 == sorted[i]) {   // long avoids int overflow
                run++;
            } else {
                run = 1;
            }
            best = Math.max(best, run);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{10, 4, 20, 1, 2, 8, 9, 3, 19}));
        System.out.println(longestConsecutive(new int[]{0, -2, 3, -1, 2, 1}));
        System.out.println(longestConsecutive(new int[]{1, 1, 2, 2, 3}));
    }
}

Output

4
6
3

Time: O(n log n). Space: O(n) for the sorted copy.

Optimal: count only from the start of each run

Put every value into a HashSet<Long>. A value x starts a run if x - 1 isn't in the set. Only from those values, count upwards while x + 1, x + 2, ... are in the set.

Each value is visited by at most one counting loop (the one of the run it belongs to), so all the loops together take O(n) steps, even though there's a loop inside a loop.

Java

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

public class Main {
    static int longestConsecutive(int[] nums) {
        Set<Long> set = new HashSet<>();
        for (int x : nums) set.add((long) x); // long values: x - 1 and x + len cannot wrap
        int best = 0;
        for (long x : set) {
            if (set.contains(x - 1)) continue; // not the start of a run
            int len = 1;
            while (set.contains(x + len)) {
                len++;
            }
            best = Math.max(best, len);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{10, 4, 20, 1, 2, 8, 9, 3, 19}));
        System.out.println(longestConsecutive(new int[]{0, -2, 3, -1, 2, 1}));
        System.out.println(longestConsecutive(new int[]{1, 1, 1}) + " " + longestConsecutive(new int[]{}));
        System.out.println(longestConsecutive(new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE}));
    }
}

Output

Time: O(n) on average. Space: O(n).

The set holds Long values, and x + len mixes a long and an int, which Java widens to long. contains takes an Object, so passing an int would box it to an Integer, which never equals a Long. Iterating over set instead of nums matters when the input has many duplicates: [1, 1, 1, ..., 2, 3, ...] would otherwise start the same count once per copy.

Edge cases

Empty array: 0.
Duplicates: counted once.
Values near Integer.MAX_VALUE or Integer.MIN_VALUE: x + len or x - 1 in int wraps around silently, which can join two unrelated values into one run. The optimal code stores long values to avoid this, and the last example shows both limits together giving 1.