Longest Consecutive Sequence

NeetCode: Longest Consecutive Sequence · LeetCode: 128. Longest Consecutive Sequence · Difficulty: Medium

Given an unsorted array nums, return the length of the longest sequence of consecutive integers (like 3, 4, 5, 6). The elements need not be adjacent in the array. Aim for O(n) time.

Example

Text

Input:  nums = [2, 20, 4, 10, 3, 4, 5]    Output: 4    (2, 3, 4, 5)
Input:  nums = [0, 3, 2, 5, 4, 6, 1, 1]   Output: 7    (0 through 6)

Brute force: sort and scan

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

Java

import java.util.Arrays;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        int best = 1;
        int run = 1;
        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i] == sorted[i - 1]) {
                continue;
            }
            if (sorted[i] - sorted[i - 1] == 1) {
                run++;
            } else {
                run = 1;
            }
            best = Math.max(best, run);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestConsecutive(new int[]{2, 20, 4, 10, 3, 4, 5}));
        System.out.println(s.longestConsecutive(new int[]{0, 3, 2, 5, 4, 6, 1, 1}));
        System.out.println(s.longestConsecutive(new int[]{}));
    }
}

Output

4
7
0

The clone() keeps the caller's array unsorted. The difference test sorted[i] - sorted[i - 1] == 1 can overflow for values at opposite ends of the int range, so inputs that reach both ends of the int range would need long for that difference.

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

Optimal: HashSet, start only at sequence beginnings

Put all numbers in a HashSet<Integer>; duplicates collapse into one entry. A number x starts a sequence only if x - 1 is not in the set. For those starting points, count upward (x + 1, x + 2, ...) while the numbers exist. Every number is visited by at most one counting loop, so the total work is linear despite the nested loop.

Java

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

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) {
                continue; // not the start of a sequence
            }
            int length = 1;
            while (set.contains(x + length)) {
                length++;
            }
            best = Math.max(best, length);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestConsecutive(new int[]{2, 20, 4, 10, 3, 4, 5}));
        System.out.println(s.longestConsecutive(new int[]{0, 3, 2, 5, 4, 6, 1, 1}));
        System.out.println(s.longestConsecutive(new int[]{}));
    }
}

Output

4
7
0

Time: O(n) expected. Space: O(n).

The loop over set visits the values in an unspecified order. The answer does not depend on that order. The expressions x - 1 and x + length stay inside int for the problem's value limits.