Longest Consecutive Sequence

Sum of Two Integers

Search in Rotated Sorted Array

Find the length of the longest run of consecutive integers in an unsorted array.

Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence (a run of consecutive integers, not necessarily contiguous in the array). You must write an algorithm that runs in `O(n)` time.

**Input / output**
- Input: `nums: integer[]` (unsorted, may contain duplicates)
- Output: `integer`, the length of the longest run of consecutive values

**Examples**
1. `nums = [100, 4, 200, 1, 3, 2]` returns `4` because the longest run is `[1, 2, 3, 4]`.
2. `nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]` returns `9` because the longest run is `[0, 1, 2, 3, 4, 5, 6, 7, 8]`.
3. `nums = []` returns `0`.

**Constraints**
- `0 <= nums.length <= 100,000`
- `-1,000,000,000 <= nums[i] <= 1,000,000,000`

**Follow-up**
Why does only starting a run when `n - 1` is absent from the set guarantee `O(n)` total work instead of `O(n^2)`?

- Find the length of the longest run of consecutive integers present in `nums` (order in the array doesn't matter, only which values exist).
- The obvious approach — sort, then scan for runs — works and is easy to explain, but costs `O(n log n)`.
- The problem explicitly asks for `O(n)`, which rules out sorting and requires a hash-set-based approach instead.

Understanding the Problem

- Put every number into a hash set for `O(1)` membership checks.
- For each number `x` in the set, only try to extend a sequence starting at `x` if `x - 1` is **not** in the set — that means `x` is the smallest element of its consecutive run, so it's a valid starting point.
- This guarantees each run is only walked once (from its start), not once per element in it, which is what keeps the overall algorithm `O(n)` despite the inner `while` loop.

Hash Set + "Start of Sequence" Check

- From a valid start `x`, keep checking `x + 1`, `x + 2`, ... as long as they're in the set, counting the run's length.
- Track the maximum run length seen across all valid starting points.
- Because every element is visited at most twice total (once as a candidate start check, once while extending a run it belongs to), the total work across all iterations stays linear.

Extending Each Run

`O(n)` time (each element examined a constant number of times) and `O(n)` space for the hash set — meets the problem's stated time complexity requirement.

Final Solution (all languages)

- Forgetting the `x - 1 not in num_set` guard and extending from every element — still produces the correct answer, but degrades to `O(n^2)` worst case (e.g. one big consecutive run) since every element re-walks the whole run.
- Using a sorted approach when `O(n)` is explicitly required — mention the tradeoff even if you start there, then optimize to the hash-set version.
- Follow-ups: how would you also return the actual sequence, not just its length? How does the approach change if duplicates should count once (the hash set already handles this for free)?