Longest Consecutive Sequence in O(n).

Problem. Given an unsorted array nums, return the length of the longest run of consecutive integers (e.g. [100,4,200,1,3,2] → 4, the run 1,2,3,4). Required: O(n) time.

The tempting wrong answer — sort

Sorting and scanning for runs is O(n log n) and easy, but it explicitly violates the O(n) requirement. The interviewer asks for O(n) precisely to push you off sorting and onto a hash set.

Brute force — O(n³)

For each value, keep probing x+1, x+2, … by linearly scanning the array for each. Cubic. Useless except as a baseline.

Optimal — HashSet, count only from sequence starts — O(n)

Put everything in a HashSet for O(1) membership. The key trick: only begin counting a run at its start, i.e. a value x for which x-1 is not in the set. From a true start, walk x+1, x+2, … upward.

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);          // dedup + O(1) lookups

    int best = 0;
    for (int n : set) {
        if (set.contains(n - 1)) continue;  // not a start; skip
        int length = 1;
        int current = n;
        while (set.contains(current + 1)) {  // walk the run upward
            current++;
            length++;
        }
        best = Math.max(best, length);
    }
    return best;
}

Why it's O(n), not O(n²)

The inner while looks nested, but the set.contains(n - 1) guard means we only enter it from the smallest element of each run. Every element is therefore visited by the inner loop at most once across the entire execution. Total work is O(n) set operations. Iterating set (not nums) also dedups, so duplicates don't inflate the count.