Longest Consecutive Sequence

Longest run of consecutive integers, regardless of order in the array. [102,4,100,1,101,3,2,1,1] → 4 (the sequence [1,2,3,4]). (LeetCode 128)

Brute force: for each element x, linearly search for x+1, x+2, … — O(n²).

Better — sort first: consecutive numbers become adjacent. Track a running streak, resetting whenever the gap to the previous distinct element isn’t exactly 1 (and skipping exact duplicates). O(n log n).

Optimal — HashSet, no sorting: insert every element into a set. x is the start of a sequence only if x - 1 isn’t in the set. For each such start, count forward (x+1, x+2, …) while those values exist in the set.

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;

    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) numSet.add(num);

    int longest = 0;

    for (int num : numSet) {
        if (!numSet.contains(num - 1)) { // start of a sequence
            int currentNum = num;
            int currentStreak = 1;

            while (numSet.contains(currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }

            longest = Math.max(longest, currentStreak);
        }
    }

    return longest;
}

Time: O(n) — every element is processed at most twice (once as a potential sequence start, once while extending some sequence). Space: O(n).