Longest increasing subsequence

The problem it solves

Given a sequence, find the longest chain of values that climbs strictly upward as you read left to right — skipping as many elements as you like, but never reordering. In [4, 2, 9, 1, 5, 8] the answer is 2, 5, 8 (or 4, 5, 8): length 3. That “skipping allowed” clause makes this a subsequence problem, and it changes everything: windows and two-pointer tricks, which live off contiguity, are useless here, and the search space is all 2ⁿ subsets.

LIS earns its canonical status three ways. It is the cleanest possible demonstration of the DP state-design question — what must a subproblem remember to be extendable? — whose answer here (“the chain must end at a known element”) transfers to dozens of harder problems. It is the engine inside real tasks: envelope/box nesting (sort one dimension, LIS the other), version-history reconciliation, patience solitaire, and the diff algorithms that find what didn’t change. And it has a famous O(n log n) upgrade whose cleverness only makes sense after the O(n²) table is understood — which is the version the player draws.

The intuition — and where it breaks down

Each element asks one question of its past: which already-finished chain am I allowed to extend, and which of those is longest? “Allowed” means the chain’s last element is smaller than me — a chain ending in 9 is dead to a 5, no matter how long it is. So walk your predecessors, keep the best chain among the strictly smaller ones, and declare your own chain to be that plus yourself. Elements with no smaller predecessor start a fresh chain of length one.

The subtle move — the one the visualization’s pick-question drills — is that you do not extend the longest chain seen so far; you extend the longest chain whose endpoint is below you. In the walkthrough below, a tall early bar carries a long chain that later small bars simply cannot touch. The greedy misreading (“track the best chain and append when possible”) fails precisely there, and recognising why it fails is the state-design lesson: a subproblem summarised as “best chain among the first i elements” has forgotten the one fact — its final value — needed to extend it. Define instead “best chain ending at i” and extension becomes a comparison.

Where the intuition stops: this formulation is quadratic, since each element interrogates all predecessors. The O(n log n) patience method reorganises the same information — smallest possible tail per chain length — but it is a different mental model, sketched under implementation notes rather than animated here.

Loading…

A walkthrough you can check

Take [3, 10, 2, 8, 4, 6].

1. 3: nothing before it — dp[0] = 1.
2. 10: 3 is smaller — extend it. dp[1] = 2.
3. 2: 3 and 10 are both ≥ 2? 3 is bigger, 10 is bigger — no one to extend. dp[2] = 1.
4. 8: smaller predecessors are 3 (chain 1) and 2 (chain 1); 10 is excluded despite its chain of 2. dp[3] = 2. ← The trap, sprung: the longest chain so far ends too high.
5. 4: smaller are 3, 2 — best chain 1. dp[4] = 2.
6. 6: smaller are 3, 2, 4 — and 4 carries chain 2. dp[5] = 3.

Answer 3, chain 3 → 4 → 6 (recovered by parent pointers; the player washes it through the skyline). Check your understanding: why is dp[3] = 2 built on 3 and not on 10’s longer chain? If that answer is instant, the state-design lesson has landed.

The invariant

dp[i] is the length of the longest strictly increasing subsequence that ends exactly at index i, and when element i is processed, dp[0..i−1] are final. The second half is free — the loop order visits indices left to right, and chains only look backwards. The first half, by strong induction: any chain ending at i either is a[i] alone (length 1, the initialisation) or has a penultimate element j < i with a[j] < a[i]; stripping a[i] leaves a chain ending at j, counted exactly by the final dp[j]. The recurrence takes the max over all legal j, so no chain is missed and none is over-counted.

The global answer is max over dp — the longest chain ends somewhere — and the parent array turns the lengths back into elements. Note the invariant’s fine print, enforced by a single character: < makes the chain strictly increasing; <= would admit plateaus. Interviewers flip that requirement mid-question to see whether the comparison is understood or copied.

Complexity, derived

Element i interrogates i predecessors: Σi = n(n−1)/2 comparisons — O(n²) time, visible in the counters panel, with O(n) space for dp and parents. The player’s step count is pinned to this shape by a growth test, so the claim is executable, not rhetorical.

The O(n log n) version changes the bookkeeping, not the answer: maintain tails[k] = the smallest value that ends any increasing chain of length k+1. Each new value binary-searches for the first tail ≥ it and overwrites it (or appends if it beats them all). tails stays sorted — that is the loop invariant needing proof — and its final length is the LIS length. The trade: blistering speed, but tails is not an actual chain (its elements may come from incompatible chains), so recovering the sequence itself needs parallel parent bookkeeping. Know which version the question needs: length-only at scale → patience; the chain itself, or a 20-minute interview window → the table.

What people get wrong

• Subsequence vs subarray: reading “subsequence” and writing a sliding window. The words are one letter apart and a whole algorithm apart.
• Extending the global best chain instead of the best chain ending below the current value — the walkthrough’s step 4 is the standing counterexample.
• Forgetting dp[i] = 1 initialisation: every element is a chain of itself; zero-initialised dp quietly produces off-by-one chains.
• Strict vs non-strict: < vs <= changes the answer on any input with duplicates; in the patience version the same flip is lower-bound vs upper-bound in the binary search.
• Claiming patience sorting’s tails is the LIS: it has the right length and is genuinely increasing, but its elements generally do not form a valid chain of the original sequence. Stating this unprompted is a strong signal; claiming the opposite is a red flag.
• O(n log n) under pressure, fumbled: the binary-search variant mis-remembered is worth less than the quadratic variant understood. Choose deliberately.

Implementation notes

The table version should look like the displayed code: two loops, one comparison, dp and parent arrays. Reconstruction: follow parents from the argmax of dp, then reverse. Ties in “best predecessor” are broken toward the earliest — deterministic output matters for testing, and the trace’s referee (the pick-question’s answer key) uses the same tie-break as the loop.

Patience sorting in six lines: for each value, binary-search tails for the first element ≥ value (lower bound); replace it, or append if none. Length of tails is the answer. For the actual sequence, also record for each value the index it landed at and a back-pointer to the previous stack’s current top, then unwind from the last append. The name comes from the card game: piles of descending cards, each new card on the leftmost pile whose top is ≥ it — pile count is the LIS length, a fact worth one delightful minute of a systems-design conversation.

Related reductions worth having ready: longest non-decreasing — switch to upper-bound; longest decreasing — negate values; envelope nesting — sort by width ascending and height descending (the descending tie-break prevents same-width envelopes chaining), then LIS heights.

The follow-up questions

Why “ending at i” rather than “within the first i”? Extendability. “Within the first i” forgets its final value, which is the only fact a future element needs. State that carries the extension information is the whole design discipline this problem teaches.

Sketch the O(n log n) version. tails[k] = smallest tail of any chain of length k+1; binary-search-and-replace per element; the array stays sorted, its length is the answer. Reconstruction needs extra parents — tails itself is not a chain.

Strict or non-strict — what changes? One comparison in the table; lower-bound vs upper-bound in patience. On duplicate-free inputs, nothing; with duplicates, everything.

Where does LIS appear outside puzzles? Diffing (LIS of matching-line indices ≈ what stayed put), envelope/box nesting after a sort, scheduling with precedence by two keys, and patience solitaire — which is not an application so much as the algorithm wearing cards.