Longest Consecutive Sequence

Problem

You are given an unsorted array of integers nums. Find the length of the longest run of consecutive integers that all appear in the array, regardless of their positions. For example, if 8, 9, 10, 11 are all present somewhere in the array, that run has length 4. Aim for linear time.

• The array may be empty and has at most 150,000 elements.
• Values can be large in either direction (magnitudes up to a billion), so an array indexed by value is not an option.

Examples

• nums = [42, 11, 9, 12, 50, 10, 8] → 5. The run 8, 9, 10, 11, 12 is present.
• nums = [-2, 6, 3, -1, 5, 4, 0, 1, 2, -2] → 9. Every value from -2 through 6 appears; the duplicate -2 does not extend the run.
• nums = [] → 0. No elements, no run.

Hints

1. Sorting makes runs obvious but costs O(n log n). What data structure gives O(1) "is value v present?"
2. If you start extending a run from every element, you will do redundant work. Which elements are worth starting from?
3. Only start from values whose predecessor v - 1 is absent; those are exactly the left ends of runs.