Longest Increasing Subsequence

mediumTests passed 2026-11-11v1.0.0
TC: O(N log N)|SC: O(N)
1D DPBinary SearchOriginal Statement (leetcode).md

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

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

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)

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.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Longest Increasing Path in a Matrix (O(M * N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.