LeetCode 354: Russian Doll Envelopes

Problem Restatement

We are given a list of envelopes.

Each envelope has:

[width, height]

One envelope can fit inside another only if both dimensions are strictly smaller.

That means:

w1 < w2
and
h1 < h2

We want the maximum number of envelopes we can nest inside each other.

This is called the Russian doll property.

We may reorder the envelopes in any way.

Input and Output

Example function shape:

def maxEnvelopes(envelopes: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

One valid nesting chain is:

[2,3] -> [5,4] -> [6,7]

Length:

3

So the answer is:

3

Example 2:

envelopes = [[1,1],[1,1],[1,1]]

No envelope can fit into another because equal dimensions are not allowed.

So the answer is:

1

First Thought: Dynamic Programming

A direct idea is:

1. Sort the envelopes.
2. Use DP similar to longest increasing subsequence.

Let:

dp[i]

mean:

maximum nesting chain ending at envelope i

Transition:

if envelopes[j] fits into envelopes[i]:
    dp[i] = max(dp[i], dp[j] + 1)

This works.

But the complexity is:

O(n^2)

For large input, we need something faster.

Key Insight

The problem becomes much simpler after sorting carefully.

Suppose we sort by:

1. Width ascending
2. Height descending when widths are equal

Example:

[[2,3],[5,4],[6,7],[6,4]]

becomes:

[[2,3],[5,4],[6,7],[6,4]]

Actually after applying the correct rule:

sorted(envelopes, key=lambda x: (x[0], -x[1]))

the result is:

[[2,3],[5,4],[6,7],[6,4]]

Now focus only on heights:

[3, 4, 7, 4]

The problem becomes:

find the longest strictly increasing subsequence

Why does descending height for equal widths matter?

Suppose we had:

[[6,4],[6,7]]

If heights were ascending, LIS on heights would incorrectly allow:

4 -> 7

But widths are equal, so nesting is illegal.

Sorting equal widths by descending height prevents this mistake.

After sorting:

[[6,7],[6,4]]

Now heights are:

[7,4]

which cannot form an increasing subsequence.

This converts the 2D problem into a 1D LIS problem.

Algorithm

Step 1:

Sort envelopes by:

(width ascending, height descending)

Step 2:

Extract all heights.

Step 3:

Compute LIS on heights.

Use the standard patience sorting method.

Maintain:

tails

where:

tails[i] = smallest possible tail of an increasing subsequence of length i + 1

For every height:

1. Binary search its insertion position in tails
2. Replace that position
3. If the height is larger than all tails, append it

The length of tails is the answer.

Correctness

After sorting, widths are non-decreasing.

For envelopes with equal widths, heights are sorted in descending order.

Therefore, any increasing subsequence in heights cannot contain two envelopes with the same width. If two equal-width envelopes appeared in the subsequence, their heights would decrease rather than increase.

So every strictly increasing subsequence of heights corresponds to a valid sequence where both width and height increase strictly.

Conversely, every valid nesting sequence must also have strictly increasing heights after sorting, so it forms an increasing subsequence in the height array.

Therefore, the problem reduces exactly to finding the LIS of heights.

The patience sorting LIS algorithm maintains:

tails[k]

as the minimum possible ending value of an increasing subsequence of length k + 1.

Replacing larger tails with smaller ones preserves all achievable subsequence lengths while keeping future extension possibilities as flexible as possible.

Therefore, the final length of tails equals the maximum valid nesting depth.

Complexity

Let n be the number of envelopes.

The binary search inside LIS gives logarithmic updates.

Implementation

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        tails = []

        for _, height in envelopes:
            pos = bisect_left(tails, height)

            if pos == len(tails):
                tails.append(height)
            else:
                tails[pos] = height

        return len(tails)

Code Explanation

First we sort:

envelopes.sort(key=lambda x: (x[0], -x[1]))

Widths increase normally.

Equal widths use descending heights.

Then we process heights only:

for _, height in envelopes:

The tails array stores the smallest ending height for every subsequence length.

Suppose:

tails = [3, 5, 8]

This means:

Now insert height 6.

Binary search gives:

pos = 2

because 6 should replace 8.

New tails:

[3, 5, 6]

This is better because a smaller tail is easier to extend later.

If the new height is larger than every tail:

tails.append(height)

which increases the LIS length.

Finally:

return len(tails)

Testing

def run_tests():
    s = Solution()

    assert s.maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]) == 3

    assert s.maxEnvelopes([[1,1],[1,1],[1,1]]) == 1

    assert s.maxEnvelopes([[1,1],[2,2],[3,3],[4,4]]) == 4

    assert s.maxEnvelopes([[4,5],[4,6],[6,7],[2,3],[1,1]]) == 4

    assert s.maxEnvelopes([[2,3],[5,4],[6,4],[6,7]]) == 3

    assert s.maxEnvelopes([[30,50],[12,2],[3,4],[12,15]]) == 3

    print("all tests passed")

run_tests()

Test meaning: