# Longest Consecutive Sequence

- **Canonical ID**: `longest-consecutive-sequence`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-consecutive-sequence
- **Difficulty**: medium
- **Patterns**: Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-consecutive-sequence/

## 1. Core Invariant / The Trick

Put all numbers in a Set. Iterate over set elements (not the raw array to skip duplicates), and ONLY start expanding `x, x+1, x+2...` if `x - 1` is NOT in the set (marking `x` as a sequence head).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(N)`
- **Proof**: Every element in the set is visited at most twice (once in outer loop, at most once in inner expansion from its sequence start).

## 3. Minimal Idiomatic Code

### Python
```python
def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for x in num_set:
        if x - 1 not in num_set:
            length = 1
            while x + length in num_set:
                length += 1
            best = max(best, length)
    return best
```

### TypeScript
```typescript
export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (!set.has(x - 1)) {
      let len = 1;
      while (set.has(x + len)) len++;
      if (len > best) best = len;
    }
  }
  return best;
}
```

### C++
```cpp
int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int x : s) {
        if (!s.count(x - 1)) {
            int y = x + 1;
            while (s.count(y)) y++;
            best = max(best, y - x);
        }
    }
    return best;
}
```

### Java
```java
int longestConsecutive(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int x : nums) s.add(x);
    int best = 0;
    for (int x : s) {
        if (!s.contains(x - 1)) {
            int y = x + 1;
            while (s.contains(y)) y++;
            best = Math.max(best, y - x);
        }
    }
    return best;
}
```

### Go
```go
func longestConsecutive(nums []int) int {
    s := make(map[int]bool, len(nums))
    for _, x := range nums { s[x] = true }
    best := 0
    for x := range s {
        if !s[x-1] {
            l := 1
            for s[x+l] { l++ }
            if l > best { best = l }
        }
    }
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Iterating over `nums` instead of `numSet` causes O(N^2) if a sequence head is duplicated many times.

### Follow-ups
- Dynamic stream additions: maintain interval boundaries `{ num: length }` merging `left` and `right` endpoints.