Longest Increasing Subsequence & the Block Reorderer
In short: the longest increasing subsequence (LIS) is the longest run of
elements that keeps the original order but may skip some. A quadratic table,
best[i] = the longest rising run ending at i, finds it in O(n²). A faster
version keeps one number per length — the smallest possible ending value,
the tails row — and finds the length alone in O(n log n) with binary search.
The tails row is not the subsequence itself; only its length is the answer.
Quarry keeps every stored document as a list of numbered blocks, and its index
expects those numbers in ascending order. After a restore from backup, the
index comes back scrambled: [4, 1, 6, 2, 7, 3, 8, 5]. Rewriting a block is
slow, so Quarry wants to leave as many blocks where they are as it can and move
the rest. The blocks that can stay are the ones that are already in order
relative to each other. The longest such group is the longest increasing
subsequence, and everything outside it has to move.
This section ends with Quarry's diff engine, which shows what changed between two revisions of a document. Every lesson fills a table, starting here with the smallest: a single row.
Subsequence, not subarray
A subarray is a contiguous slice. A subsequence keeps the original order
but may skip elements. In [4, 1, 6, 2, 7, 3, 8, 5], the blocks 1, 2, 3, 5
form a rising subsequence even though other blocks sit between them. They can
all stay put: move the other four blocks into the gaps and the index is sorted.
The brute-force plan is to try every subsequence and keep the longest rising
one. Each element is either in or out, so a list of n elements has 2ⁿ
subsequences. Count just the rising ones in a short list first:
from itertools import combinations
blocks = [4, 1, 6, 2]
rising = 0
for size in range(1, len(blocks) + 1):
for pick in combinations(blocks, size):
if all(a < b for a, b in zip(pick, pick[1:])):
rising += 1
print(rising)The quadratic table: best run ending here
Instead of searching over subsequences, ask a smaller question about every position:
best[i]= the length of the longest rising subsequence that ends at positioni.
A run that ends at i is either nums[i] alone (length 1), or a run ending at
some earlier j with nums[j] < nums[i], extended by one. So:
best[i] = 1 + max(best[j] for j < i if nums[j] < nums[i]), or 1 when no such
j exists.
The answer is the largest value anywhere in best, not the last one,
because the longest run can end anywhere.
Watch the row fill. Each arrow points from the earlier run that a cell extends:
Each best[i] reads every earlier cell with a smaller block and extends the longest one, which is why this version costs O(n²).
Block 4 has nothing before it, so the best run ending there is just itself: 1. 2 by 8 table. At row 1, column 0 — value 1. 9 of 16 cells filled.
Each cell looks at every cell to its left, so the total work is
0 + 1 + 2 + … + (n − 1), about n²/2 comparisons: O(n²) time. The only
storage is the best row itself, one number per position: O(n) space.
nums = [3, 1, 4, 1, 5]
best = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i] and best[j] + 1 > best[i]:
best[i] = best[j] + 1
print(best)Here's a first attempt that reads the answer from the wrong cell:
The longest rising run in [2, 5, 3, 7, 1] is 2, 5, 7 (or 2, 3, 7), length 3, but this prints 1. Fix the return so it reports the best run wherever it ends.
❓ Cross-question: "Why not walk left to right and keep each block that's bigger than the last one kept?" Because one early block can block the rest:
blocks = [9, 1, 2, 3, 4]
kept = []
for b in blocks:
if not kept or b > kept[-1]:
kept.append(b)
print(len(kept))The tails row: O(n log n)
The quadratic table stores one number per position. A faster idea stores one number per length:
tails[k]= the smallest block that ends any rising run of lengthk + 1seen so far.
A small tail is better than a big one, because more future blocks can follow it.
Two facts make this fast. First, tails is always sorted. Second, a new block
x changes exactly one cell. It replaces the first tail that is ≥ x,
since x makes a smaller ending for that length. If no tail is ≥ x, it
extends the longest run, so it's appended. Finding "the first tail ≥ x" in a
sorted list is binary search, which the bisect module already does. (Deal the
blocks onto piles like a card game and the pile tops are this row, which is why
it's also called patience sorting.)
Every block either overwrites one tail with something smaller or appends a new longest length. The row's length is the answer, but the row itself is not a subsequence.
Block 4 starts the row: the best run of length 1 ends in 4. 1 cell. At index 0.
Each of the n blocks does one binary search over a row no longer than itself:
O(n log n) time, and the row holds at most n numbers: O(n) space, same
as the quadratic version — the speed-up is in time, not memory.
Step through the row on a short input. Watch k, and notice that tails never
gets longer unless k equals its length:
The commonest mistake with this algorithm is to print tails and call it the
subsequence:
from bisect import bisect_left
tails = []
for x in [3, 5, 7, 1]:
k = bisect_left(tails, x)
if k == len(tails):
tails.append(x)
else:
tails[k] = x
print(tails)Strictly rising, or allowed to repeat?
bisect_left finds the first tail ≥ x, so an equal value replaces a tail
and can't extend a run. That is strictly increasing. For a non-decreasing run,
where equal values may sit next to each other, use bisect_right, which finds
the first tail > x. Then an equal value lands after its twin and extends.
That one-word change is the build exercise below.
Your own fill, drawn
Edit nums and run it. The second row is best, filled by your own loop. Try
a list that only falls, one that only rises, and one with repeats.
Your loop fills best one cell at a time. The answer is the biggest cell, wherever it sits.
How much faster is the tails row?
The table does about n²/2 comparisons and the tails row about n · log₂ n.
Their ratio grows with n:
| blocks n | table (n²/2) | tails row (n · log₂ n) | ratio |
|---|---|---|---|
| 100 | 5,000 | 664 | 7.5× |
| 1,000 | 500,000 | 9,966 | 50× |
| 1,000,000 | 5 × 10¹¹ | about 20 million | 25,000× |
At a million blocks that's the gap between instant and a very long wait.
Idioms & real-world patterns
Fewest moves to sort
Any element not on a longest rising run has to move, and every element on it
can stay. So "fewest single moves to sort a list" is n − LIS: the Quarry
block reorderer you are about to build.
Two keys at once
When two things must grow together, such as boxes that are both wider and deeper, sort by the first key and run LIS on the second. Ties on the first key are the trap in the boss exercise.
Where knapsack fits
Every DP in this section makes a choice at each cell: extend this run or start a new one, match or skip, insert or delete. The plain "take this item or leave it" choice under a budget is knapsack. You built it in section 6 as Tunebox's best playlist, and it returns in Planning DP. This section doesn't repeat it. Here the choices are about order.
Quick practice
from bisect import bisect_left
tails = []
for x in [2, 2, 2]:
k = bisect_left(tails, x)
if k == len(tails):
tails.append(x)
else:
tails[k] = x
print(tails)The longest strictly rising run in [3, 3, 3, 4] is 3, 4, length 2, but this prints 4. Fix the bisect call.
🎯 Your turn
Write fewest_moves(order). order is a list of distinct block numbers in their
current storage order. One move takes a block out and puts it back anywhere.
Return the fewest moves that leave the list in ascending order.
fewest_moves([4, 1, 6, 2, 7, 3, 8, 5])→4(keep 1, 2, 3, 5)fewest_moves([1, 2, 3])→0fewest_moves([])→0
Use the tails row so that it stays fast on a long index.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅