Longest increasing subsequence

42 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Heights of eight people in a line: 10, 9, 2, 5, 3, 7, 101, 18. Pick some of them, keeping their order, so that heights strictly increase. How long can the pick be? By hand you find 2, 5, 7, 101 or 2, 3, 7, 18: four people. Could it be five? You check and no.

The obvious method keeps, for each person, the longest increasing pick that ends with them, by looking at everyone before them. That is n comparisons per person, n² in total: for 100,000 people, 10 billion. There is a trick that reduces each person's work to a single binary search.

Build the structure, one piece at a time

Piece one: think of dealing cards onto piles, the game of patience. Each new height goes onto the leftmost pile whose top is at least as big as it; if no pile qualifies, start a new pile on the right. The number of piles at the end is the answer.

Piece two: you do not need the piles, only their tops. Keep an array tails where tails[k] is the top of pile k, that is, the smallest possible last height of an increasing pick of length k + 1.

Piece three: tails is always sorted, so "leftmost pile whose top is at least this height" is a binary search for the first entry ≥ the new height. Replace that entry, or append if none.

Length 4. Note that tails itself is not always a valid pick; it is a record of the best possible endings.

Why it is correct

The invariant: tails[k] is the smallest last element among all increasing picks of length k + 1 seen so far, and tails is strictly increasing. When a new height x arrives and the first entry ≥ x is at position k, every entry before it is smaller than x, so a pick of length k exists ending below x, and extending it gives a pick of length k + 1 ending at x; since x ≤ tails[k], writing x there keeps the entry minimal. Sortedness survives because x is larger than tails[k − 1] and no larger than the old tails[k]. Appending happens exactly when x beats every top, which is a genuinely longer pick. So the length of tails is the length of the longest increasing pick.

Why it is fast

One binary search over at most n entries per person:

work = n log₂ n, about 1.7 million steps for 100,000 people instead of 10 billion

How to recognise it in an interview

Cues: "longest increasing subsequence", "nested" or "fits inside" objects sorted by one dimension, "longest chain", "minimum removals to make it sorted". The first thing to say: "I will keep the smallest possible tail for each length and binary-search where each element lands." Longest Increasing Subsequence is the example above. Russian Doll Envelopes sorts envelopes by width ascending and height descending, then runs this on the heights, so two envelopes of equal width can never nest.

02The idea in one line

Patience piles: binary search where each number lands; pile count is the LIS length.

Reach for it when: LIS, Russian doll envelopes, number of LIS, longest chain, bitonic.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: LIS on [10,9,2,5,3,7,101,18]. These are its captions in order, so you can follow without the video or check a step you missed.

1. tails stays sorted: binary search where each number lands
2. 10 is bigger than every tail: append, length 1
3. 9 replaces tails[0] = 10: same length, smaller tail
4. 2 replaces tails[0] = 9: same length, smaller tail
5. 5 is bigger than every tail: append, length 2
6. 3 replaces tails[1] = 5: same length, smaller tail
7. 7 is bigger than every tail: append, length 3
8. 101 is bigger than every tail: append, length 4
9. 18 replaces tails[3] = 101: same length, smaller tail
10. Length of tails = 4 (e.g. 2, 3, 7, 101); tails itself is not the subsequence
11. One binary search per element: O(n log n)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).