Russian Doll Envelopes

Russian Doll Envelopes is the 2-D version of "longest increasing subsequence." One envelope fits inside another only if both its width and height are strictly larger. The trick is to collapse the second dimension away with a clever sort, then solve the rest as a plain LIS.

The slow way first

You could try every ordering of envelopes and see which nest — exponential, hopeless. A smarter brute force sorts by width and runs an O(n²) LIS on the heights. That passes small inputs but is too slow when there are many envelopes.

The question to ask: can I reduce this 2-D nesting to a 1-D problem I already know? If I sort by width, then nesting only depends on heights — and "strictly increasing heights" is exactly LIS.

The idea: sort away one dimension, then run LIS

Sort the envelopes by width ascending. For ties (equal widths), sort by height descending. That tie-break is the whole trick: two envelopes with the same width can never nest, and descending heights guarantee the LIS will never pick two of them. Now the answer is the Longest Increasing Subsequence of the heights, which patience sort solves in O(n log n).

Patience sort keeps an array tails, where tails[k] is the smallest possible tail of an increasing run of length k+1. For each height we binary-search: if it beats every tail we append (the longest run grew); otherwise we overwrite the first tail that is not smaller (keeping that length but with room to grow later).

Walk through it

Step through the animation. The cells show the heights after sorting: (2,3) (5,4) (6,7) (6,4) → [3, 4, 7, 4]. Heights 3, 4, 7 each beat the current last tail, so tails grows to length 3. The final 4 (the duplicate-width envelope) does not beat 7, so it only overwrites tails[1] — the length stays 3. That is the answer.

Pseudocode

sort envelopes by (width ascending, height descending)
tails = empty list
for each (w, h) in envelopes:
    pos = first index in tails whose value is >= h   # binary search
    if pos == len(tails):
        append h          # h beats every tail -> longest run grew
    else:
        tails[pos] = h    # overwrite, keep length, lower the tail
return len(tails)

The Python solution

def max_envelopes(envelopes):
    envelopes.sort(key=lambda e: (e[0], -e[1]))
    tails = []
    for w, h in envelopes:
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] < h: lo = mid + 1
            else: hi = mid
        if lo == len(tails): tails.append(h)
        else: tails[lo] = h
    return len(tails)

• Line 2 is the heart of the trick: width ascending, height descending within equal widths.
• tails holds the smallest tail seen for each achievable run length.
• The while loop is a binary search for the first tail >= h (this is bisect_left written out).
• If lo runs past the end, h is bigger than every tail, so we append and the longest run grows.
• Otherwise we overwrite tails[lo] — same length, but a smaller tail leaves more room ahead.
• len(tails) is the length of the longest strictly increasing run of heights, the answer.

Complexity

The naive LIS over heights is O(n²); patience sort with binary search brings the whole thing down to O(n log n).

When this pattern shows up

Practice