# Longest Consecutive Sequence

[link](https://leetcode.com/problems/longest-consecutive-sequence/) · Medium · `array`, `hash set`, `union find`

> "longest run of consecutive values in O(n), original order doesn't matter" → put everything in a hash set and only start counting at run starts (x - 1 not in set). A nested while is still O(n) total when each element is walked at most once: argue it by amortization, not by counting loop depth.

## Problem

> Given an array of integers `nums`, return the length of the longest consecutive sequence of
> elements that can be formed. A consecutive sequence is a sequence of elements in which each
> element is exactly 1 greater than the previous element. The elements do not have to be
> consecutive in the original array.
>
> You must write an algorithm that runs in $O(n)$ time.

**Example 1**
```
Input:  nums = [2, 20, 4, 10, 3, 4, 5]
Output: 4          # [2, 3, 4, 5]
```

**Example 2**
```
Input:  nums = [0, 3, 2, 5, 4, 6, 1, 1]
Output: 7          # [0, 1, 2, 3, 4, 5, 6]
```

**Constraints**
- `0 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`

## Thinking

- **Brute force idea:** treat every element as the start of a sequence and count up with
  `x + 1 in nums`. With a list lookup that's $O(n^3)$; with a set it's still $O(n^2)$ because
  every element of a long run re-walks the rest of the run.
- **Sorting idea:** sort, then scan once counting runs (skip duplicates, reset on a gap):
  $O(n \log n)$. Correct and simple, but breaks the $O(n)$ requirement.
- **Key insight:** only walk from the **start of a sequence**: `x` is a start iff `x - 1` is
  **not** in the set. Then each number is visited once by the `for` loop and at most once by a
  `while` walk, so the total work is $O(n)$ (amortized, even though there's a nested loop).
- **Loop over the set, not the list.** With duplicates of a start value
  (`[0, 0, 0, ..., 0, 1, 2, ..., m]`) looping over `nums` re-walks the same run once per copy:
  $O(n^2)$.
- **Edge cases to remember:** empty array → `0`; duplicates (`[1, 1]` → 1, they don't extend a
  run); negatives and runs crossing 0; all elements isolated → 1; values near $\pm 10^9$
  (fine in Python, `x + 1` can't overflow).

## Solution

### Approach A — my version (hash set, walk from sequence starts)

**Complexity:** Time $O(n)$ · Space $O(n)$. This already **is** the optimal algorithm, and it
loops over the set, so duplicates can't make it quadratic. Small things only:
1. `n + 1 in nums_set` skips singletons before any walking. It costs an extra lookup per start
   but saves the `while` setup and the `max()` call, and on sparse data (most numbers isolated)
   that makes mine the **fastest** version (see section 5). The price is the `len == 0` guard
   and `counter = 1`.
2. `start` is really the **current end** of the run, and `temp_counter` duplicates what
   `start - n + 1` already tells you. One variable is enough.

The code is unchanged except for the signature and comments.

```python
def longest_consecutive_mine(nums: list[int]) -> int:
    if len(nums) == 0:                                   # needed because counter starts at 1
        return 0
    nums_set = set(nums)
    counter = 1

    for n in nums_set:                                   # good: set, not list (no duplicate re-walks)
        if n - 1 not in nums_set and n + 1 in nums_set:  # skips singletons cheaply (a speed win)
            start = n                                    # really the current end of the run
            temp_counter = 1
            while start + 1 in nums_set:
                temp_counter += 1
                start += 1
            counter = max(counter, temp_counter)
    return counter
```

### Approach B — sort and scan

**Complexity:** Time $O(n \log n)$ · Space $O(n)$ for the sorted copy.
Sort, then count runs: same value → skip, `+1` → extend, anything else → reset. Doesn't meet the
$O(n)$ requirement, but it's the natural first answer and useful when memory for a set is tight
(sorting in place needs no extra hash table).

```python
def longest_consecutive_sort(nums: list[int]) -> int:
    if not nums:
        return 0
    nums = sorted(nums)  # copy: don't mutate the caller's list
    longest = current = 1
    for prev, x in zip(nums, nums[1:]):
        if x == prev:
            continue                   # duplicate: neither extends nor breaks the run
        if x == prev + 1:
            current += 1
            longest = max(longest, current)
        else:
            current = 1
    return longest
```

### Approach C — hash set, walk only from starts ✅ best practice

**Complexity:** Time $O(n)$ · Space $O(n)$.
Approach A, tidied: no special cases, one walking variable. The `if x - 1 not in num_set` line
is the whole trick; it guarantees each run is walked exactly once.

```python
def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0
    for x in num_set:              # the set, so duplicates don't cause re-walks
        if x - 1 not in num_set:   # x starts a run
            end = x
            while end + 1 in num_set:
                end += 1
            longest = max(longest, end - x + 1)
    return longest
```

### Approach D — hash map of run lengths at the boundaries (one pass)

**Complexity:** Time $O(n)$ · Space $O(n)$.
For each new `x`, look up the run lengths ending at `x - 1` (`left`) and starting at `x + 1`
(`right`). The merged run has length `left + right + 1`; store it at `x` and at the two new
boundaries `x - left` and `x + right`. Only boundaries need to be correct, so it's $O(1)$ per
element. Same idea as union-find on consecutive numbers; useful when numbers arrive as a stream.

```python
def longest_consecutive_boundary(nums: list[int]) -> int:
    run = {}  # x -> length of the run x belongs to (only reliable at run boundaries)
    longest = 0
    for x in nums:
        if x in run:
            continue                   # duplicate
        left = run.get(x - 1, 0)
        right = run.get(x + 1, 0)
        length = left + right + 1
        run[x] = run[x - left] = run[x + right] = length
        longest = max(longest, length)
    return longest
```

## Scratch / Experiments

Two inputs at the max size $n = 10^5$:
- **random:** values from the full range $\pm 10^9$, so almost every run has length 1;
- **one run:** `range(n)` shuffled, so one run of length $n$ (the `while` walk does all the work).

Measured on my machine:

| approach | random ($\pm 10^9$) | one run |
|---|---|---|
| A, mine (set + singleton filter) | **8.9 ms** | 10.1 ms |
| B, sort | 12.8 ms | 15.7 ms |
| C, set (best practice) | 12.1 ms | **9.5 ms** |
| D, boundary map | 22.0 ms | 22.2 ms |

- **A beats C on random data.** Almost every number is a run of length 1. C still calls
  `max()` and computes `end - x + 1` for each one; A's `n + 1 in nums_set` check drops them first.
  A Python function call costs more than a set lookup, so the filter pays off. On one long run
  there's only one start, so the filter does nothing and the two are about even.
- **Sorting (B) is close** despite $O(n \log n)$: `sorted` is Timsort in C and
  $\log_2 10^5 \approx 17$ is small. Big-O says how it grows, not which wins at this size.
- **D is the slowest**, despite being one pass: it does ~4 dict operations per element and
  allocates a dict entry for each one.
- **The trap:** looping over the list is ~800× slower (122 ms vs 155 μs) on just 4000
  elements, because the run of 2000 is re-walked once for each of the 2000 copies of `0`.

The last block shows the trap from section 2: looping over **`nums`** instead of the set, with many
copies of a run's start. Shrunk to $m = 2000$ copies + a run of 2000 because it's quadratic.

```python
import random

random.seed(0)
n = 100_000
random_nums = [random.randint(-10**9, 10**9) for _ in range(n)]
one_run = list(range(n))
random.shuffle(one_run)

for label, data in [("random", random_nums), ("one run", one_run)]:
    print(f"--- {label}")
    for fn in APPROACHES:
        print(f"{fn.__name__:30s}", end=" ")
        %timeit -n 5 -r 3 fn(data)
```

```python
def longest_consecutive_loop_list(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0
    for x in nums:                 # SLOW: list, so each duplicate start re-walks its run
        if x - 1 not in num_set:
            end = x
            while end + 1 in num_set:
                end += 1
            longest = max(longest, end - x + 1)
    return longest

m = 2000
trap = [0] * m + list(range(m))    # m copies of the start 0, run length m
for fn in (longest_consecutive, longest_consecutive_loop_list):
    print(f"{fn.__name__:30s}", end=" ")
    %timeit -n 3 -r 3 fn(trap)
```

## Takeaways

- **Pattern:** "longest run of consecutive values in $O(n)$, original order doesn't matter" →
  **put everything in a hash set and only start counting at run starts** (`x - 1 not in set`).
  A nested `while` is still $O(n)$ total when each element is walked at most once: argue it by
  **amortization**, not by counting loop depth.
- **Mistakes I made:**
  - None in correctness or Big-O: my solution was already the optimal approach and correctly
    looped over the set.
  - The `n + 1 in nums_set` filter is a real optimization (it skips `max()` for every isolated
    number), but it forced a `len == 0` guard and `counter = 1`. In an interview, write the
    simple version (`longest = 0`, no guard) first; add the filter as a micro-optimization.
  - Two variables (`start`, `temp_counter`) tracked the same thing. Keep one (`end`) and compute
    the length as `end - x + 1`.
  - Remember **why** iterating the set matters: over the list, duplicates of a start value make
    it $O(n^2)$.
- **Related problems:** Contains Duplicate (#217, the same "hash set for $O(1)$ membership" step),
  Binary Tree Longest Consecutive Sequence (#298, the same "+1 chain" on a tree), Number of
  Islands (#200) / Graph Valid Tree (#261) (union-find, the idea behind Approach D), Missing
  Number (#268) and First Missing Positive (#41) (reasoning about which values are present).

---

From https://taosu.blog/notes/0128-longest-consecutive-sequence