Longest Consecutive Sequence

Longest Consecutive Sequence: given an unsorted array of integers nums, return the length of the longest run of consecutive values (x, x+1, x+2, …) that all appear in the array. The run can use the values in any order of the array. The target is O(n) time.

Example: [100, 4, 200, 1, 3, 2] returns 4, for 1, 2, 3, 4.

Sort the array and walk it, extending the current run while each value is one more than the previous (skipping duplicates). It is simple and correct, but the sort costs O(n log n). A naive alternative — for every value, count upward with a linear search for each next value — is O(n³) or O(n²) with a set.

With a set, counting upward from every value repeats work. In 1, 2, 3, 4, counting from 1 walks four values, from 2 walks three, from 3 two, from 4 one: the same run is walked four times. On a long run of n values that is O(n²).

A value starts a run exactly when its predecessor is missing:

1. Put every number in a hash set.
2. For each value num in the set, if num - 1 is in the set, skip it — its run will be counted from the start.
3. Otherwise count upward: num + 1, num + 2, … while each is in the set, and keep the longest length.

Every run is walked once, from its start, and every other value is rejected with one lookup — O(n) in total.

The set's values are drawn in sorted order so runs show up as neighbours — the algorithm itself never sorts. Watch values with a predecessor get skipped, and each run fill in from its start; the longest run so far stays highlighted.