Problem Statement
Russian Doll Envelopes
You have a bunch of envelopes. Each envelope has a width and a height. One envelope fits inside another only if it is strictly smaller in BOTH width and height. Equal sizes do not fit, the inner one has to be genuinely smaller on both sides. The question: what is the longest chain of envelopes you can nest, one inside the next, like Russian nesting dolls? The trick is to sort the envelopes so that one dimension is already handled, and then solve a simpler problem on the other dimension. First we sort by width going up. When two envelopes share the same width, we sort their heights going DOWN. After that, we only look at the heights and find the longest run that keeps increasing. That run is called the Longest Increasing Subsequence, or LIS, and we find it fast using binary search.
Signals to notice
Brute force first
All subsets — O(2^n).
The key insight
Sort by width ASC, height DESC for same width. LIS on heights. O(n log n).
Trace it on envelopes=[[5,4],[6,4],[6,7],[2,3]]
sort by width ASC, height DESC -> [2,3],[5,4],[6,7],[6,4]; heights=[3,4,7,4]; tails=[] h=3: bisect_left([],3)=0 == len(0) -> append; tails=[3] h=4: bisect_left([3],4)=1 == len(1) -> append; tails=[3,4] h=7: bisect_left([3,4],7)=2 == len(2) -> append; tails=[3,4,7] h=4: bisect_left([3,4,7],4)=1 != len(3) -> replace tails[1]=4; tails=[3,4,7] (no growth, blocks same-width 6) return len(tails)=3
What must stay true
Descending height for same width prevents two same-width envelopes in the LIS. LIS on heights gives longest valid nesting.
Shape of the loop
sort envelopes by width ASC, then height DESC
tails = []
for (_, h) in envelopes:
pos = bisect_left(tails, h)
if pos == len(tails): tails.append(h) else tails[pos] = h
return len(tails)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not sorting height descending for equal widths — allows invalid same-width pairs in the sequence.