# Longest Increasing Subsequence

- **Canonical ID**: `longest-increasing-subsequence`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-increasing-subsequence
- **Difficulty**: medium
- **Patterns**: 1D DP, Binary Search
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-increasing-subsequence/

## 1. Core Invariant / The Trick

Patience sorting (`tails` invariant): maintain `tails[k]` = smallest possible tail value of any strictly increasing subsequence of length `k + 1`. Because `tails` stays strictly sorted, replace the first element `>= x` via `bisect_left` (or append when `x` exceeds all tails).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N log N)`
- **Space Complexity**: `O(N)`
- **Proof**: Replacing a larger tail with a smaller `x` never shrinks reachable length while making future extensions strictly easier; `N` binary searches take `O(N log N)`.

## 3. Minimal Idiomatic Code

### Python
```python
def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for x in nums:
        idx = bisect.bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
    return len(tails)
```

### TypeScript
```typescript
export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      const m = (l + r) >>> 1;
      if (tails[m] < x) l = m + 1;
      else r = m;
    }
    tails[l] = x;
  }
  return tails.length;
}
```

### C++
```cpp
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}
```

### Java
```java
int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int len = 0;
    for (int x : nums) {
        int l = 0, r = len;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (tails[m] < x) l = m + 1; else r = m;
        }
        tails[l] = x;
        if (l == len) len++;
    }
    return len;
}
```

### Go
```go
func lengthOfLIS(nums []int) int {
    var tails []int
    for _, x := range nums {
        i := sort.SearchInts(tails, x)
        if i == len(tails) { tails = append(tails, x) } else { tails[i] = x }
    }
    return len(tails)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Note `tails` holds valid lengths, NOT necessarily an actual valid subsequence path (remember if asked to reconstruct, store predecessor indices alongside `tails`).
- Strict increasing uses lower-bound (`bisect_left`); non-decreasing uses upper-bound (`bisect_right`).

### Follow-ups
- Russian Doll Envelopes: sort widths ascending and heights **descending**, then compute 1D LIS on heights.