Russian Doll Envelopes: LIS with a Sorting Trick

LeetCode 354: Russian Doll Envelopes gives you a list of envelopes, each described by a width and height [w, h]. One envelope fits inside another if and only if both its width AND height are strictly smaller. Your task is to find the maximum number of envelopes you can nest inside each other, Russian-doll style.

For example, [2,3] fits inside [5,4] because 2 < 5 and 3 < 4. But [6,4] does not fit inside [6,7] because the widths are equal, not strictly smaller.

This problem is rated Hard, and for good reason. The nesting rule applies in two dimensions simultaneously, which makes the brute-force approach slow. The key is a clever preprocessing step that collapses the problem from 2D down to 1D, where you can apply a fast LIS algorithm you may already know.

Why naive DP is too slow

The O(n^2) DP approach is to check every pair of envelopes: for each envelope i, look at every earlier envelope j and ask "does j fit inside i?" If it does, update dp[i] = max(dp[i], dp[j] + 1).

This works correctly, but the constraint allows up to 100,000 envelopes. At n = 100,000, an O(n^2) approach runs roughly 10 billion operations. That will time out.

You need O(n log n).

The key insight

Sort the envelopes by width ascending, but when two envelopes share the same width, sort by height descending.

After that sort, you only need to find the Longest Increasing Subsequence (LIS) on the heights column.

Why does this work? The ascending width sort means any valid chain of envelopes must use envelopes in sorted order by width. The descending height sort for equal widths is the crucial trick: if two envelopes have the same width (say both have width 6), their heights appear in decreasing order in the sorted list. A strictly increasing subsequence can only pick at most one from any decreasing run. So the descending-height tie-breaking rule prevents you from ever selecting two envelopes with the same width, which would violate the strict nesting requirement.

Once the sort is done, any strictly increasing subsequence of heights corresponds to a valid chain of envelopes where each successive envelope has strictly greater width (because of ascending sort order) and strictly greater height (because of the LIS constraint). The length of the longest such subsequence is your answer.

The code

from bisect import bisect_left

def maxEnvelopes(envelopes):
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    tails = []
    for _, h in envelopes:
        pos = bisect_left(tails, h)
        if pos == len(tails):
            tails.append(h)
        else:
            tails[pos] = h
    return len(tails)

The sort key (x[0], -x[1]) sorts by width ascending, then by negative height (which gives descending height). After that, the inner loop is standard O(n log n) LIS via patience sorting: for each height, binary search the tails array to find the leftmost position where h can be placed, then either extend tails or replace an existing entry.

Step-by-step walkthrough

Given envelopes = [[5,4],[6,4],[6,7],[2,3]]:

After sorting by (width asc, height desc): [[2,3],[5,4],[6,7],[6,4]]

Heights extracted: [3, 4, 7, 4]

Now run patience sorting on [3, 4, 7, 4]:

The tails array ends with length 3, so the answer is 3. The actual chain is [2,3] inside [5,4] inside [6,7].

Notice step 4: height 4 tries to extend the sequence, but bisect_left finds it belongs at index 1 (replacing the existing 4). The length does not change. This is exactly the descending-height trick in action: the second envelope with width 6 ([6,4]) cannot extend the chain because its height (4) is already dominated by the earlier entry.

Complexity

The tails array holds at most n elements in the worst case (a fully increasing height sequence). The binary search over tails at each step is O(log n). Combined with the initial sort, the total time is O(n log n).

Building blocks

This problem is built on two ideas snapped together.

The first is patience sorting for LIS. Maintaining a tails array and using bisect_left to place each element in O(log n) is the same algorithm from Longest Increasing Subsequence. If you already know that problem, the inner loop here is identical.

The second is the sort-trick for dimension reduction. The descending-height tie-breaking is specific to this problem, and it is the part that most solutions get wrong if they are not careful. The insight is that when two envelopes share a width, you can never use both. By arranging equal-width envelopes in decreasing height order, you guarantee the LIS algorithm can only select one of them.

Together these two insights reduce a 2D nesting problem to a 1D LIS problem. The sort handles the 2D constraint; the LIS handles the optimization.

Edge cases

• All envelopes have the same width. After sorting, all heights appear in decreasing order. A strictly increasing subsequence of a decreasing sequence has length at most 1. The answer is 1.
• All envelopes have the same height. The widths are all different (or equal). If heights are all equal, no two envelopes can nest (strict inequality required). The answer is 1.
• Single envelope. The answer is trivially 1.
• Strictly increasing widths AND heights. Every envelope fits inside the next one. After sorting, heights are already increasing, and the LIS equals n. The answer is n.

From understanding to recall

There are two separate insights here, and forgetting either one produces a wrong answer.

If you remember the LIS reduction but forget the descending-height sort, your code will allow two envelopes with the same width in the chain. You will get a wrong answer on test cases like [[3,3],[3,4]].

If you remember the sort but try to use O(n^2) DP for the LIS, your code will time out on large inputs.

Spaced repetition is especially useful here because both insights need to be active at the same time when you sit down to code. The sort trick and the patience sorting algorithm are separate mental objects, but this problem requires you to connect them and write them together without notes. Drilling both as a pair is the most efficient way to build that recall.

Related posts

• Longest Increasing Subsequence - the core algorithm; LIS in O(n log n) via patience sorting
• Binary Search - the bisect_left mechanic used inside patience sorting
• Maximum Gap - another problem where sorting reveals a hidden structure