LeetCode Problem 354

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Sorting

Solution

LeetCode 354, Russian Doll Envelopes

Problem Understanding

The problem gives a list of envelopes, where each envelope is represented as a pair [w, h]. The value w is the width and h is the height. An envelope can fit inside another envelope only if both dimensions are strictly smaller. That means envelope A can go inside envelope B only when:

• A.width < B.width
• A.height < B.height

The task is to determine the maximum number of envelopes that can be nested inside one another, similar to Russian nesting dolls.

The important detail is that rotation is not allowed. An envelope [5, 4] cannot become [4, 5]. The width and height must stay in their original orientation.

The input size is very large. The number of envelopes can be as high as 10^5, which immediately tells us that quadratic solutions will likely be too slow. Any algorithm with O(n^2) complexity risks timing out at this scale. This strongly suggests that we need a solution close to O(n log n).

Several edge cases are important:

• Multiple envelopes may have identical dimensions.
• Multiple envelopes may share the same width but have different heights.
• Because the comparison must be strictly greater in both dimensions, envelopes with equal widths or equal heights cannot nest.
• A naive sorting strategy can accidentally allow invalid nesting when widths are equal.
• The smallest possible input contains only one envelope, in which case the answer is 1.

Understanding how equal widths behave is the key insight that makes the optimal solution work correctly.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to think of each envelope as a node in a graph or state space. For every envelope, we try placing every larger envelope after it and recursively compute the longest valid chain.

We can first sort the envelopes and then use dynamic programming:

• Let dp[i] represent the maximum nesting chain ending at envelope i.
• For every envelope i, check all previous envelopes j.
• If envelope j can fit inside envelope i, update:

dp[i] = max(dp[i], dp[j] + 1)

This works because every valid chain is explored, and the longest chain is recorded.

However, this requires checking every pair of envelopes, resulting in O(n^2) time complexity. With n = 10^5, this becomes far too slow.

Key Insight for the Optimal Solution

The critical observation is that the problem can be transformed into a variation of the Longest Increasing Subsequence problem.

Suppose we sort envelopes by:

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

After sorting this way:

• Widths are automatically handled by the ordering.
• Equal widths cannot accidentally form a valid chain because heights are descending for equal widths.
• We only need to find the Longest Increasing Subsequence on heights.

The descending sort for equal widths is extremely important.

Consider:

[5,4], [5,5]

If heights were sorted ascending, the LIS on heights would incorrectly treat 4 -> 5 as valid, even though widths are equal and nesting is illegal.

Sorting equal widths by descending height prevents this mistake because the heights become:

5, 4

which cannot form an increasing subsequence.

Once transformed, we can solve the LIS problem in O(n log n) using binary search.

Approach	Time Complexity	Space Complexity	Notes
Brute Force Dynamic Programming	O(n²)	O(n)	Checks every previous envelope for each envelope
Optimal LIS + Binary Search	O(n log n)	O(n)	Sorts carefully, then applies LIS on heights

Algorithm Walkthrough

1. Sort the envelopes by width in ascending order.

This ensures that when we process envelopes from left to right, widths never decrease. 2. For envelopes with the same width, sort heights in descending order.

This prevents envelopes with identical widths from appearing as valid increasing subsequences in height. 3. Extract the heights after sorting.

After sorting, the width constraint is already handled. The problem becomes finding the longest strictly increasing subsequence among heights. 4. Maintain a list called lis.

The value lis[i] represents the smallest possible tail value of an increasing subsequence of length i + 1. 5. Process each height one by one.

For every height:

• Use binary search to find the leftmost position where this height can be inserted.
• If the height is larger than all existing tails, append it.
• Otherwise, replace the existing value.

6. Continue until all heights are processed.

The length of lis at the end is the maximum number of nested envelopes.

Why it works

After sorting widths ascending and equal widths descending by height, any increasing subsequence in heights automatically corresponds to a valid nesting sequence.

The LIS algorithm maintains the smallest possible ending height for every subsequence length. Smaller tails are always better because they leave more room for future envelopes to extend the sequence. Binary search ensures each update is efficient while preserving correctness.

Python Solution

from typing import List
from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Sort by width ascending and height descending
        envelopes.sort(key=lambda envelope: (envelope[0], -envelope[1]))

        lis = []

        for _, height in envelopes:
            position = bisect_left(lis, height)

            if position == len(lis):
                lis.append(height)
            else:
                lis[position] = height

        return len(lis)

The implementation begins by sorting the envelopes using a custom key. Widths are sorted in ascending order, while heights for equal widths are sorted in descending order. This ordering is essential for correctness.

The lis array stores the smallest possible tail for increasing subsequences of different lengths. It does not necessarily represent an actual nesting sequence, but its length always equals the length of the longest valid subsequence found so far.

For each envelope height, bisect_left finds the first position where the height can be inserted while maintaining sorted order.

If the height is larger than all existing tails, it extends the LIS and is appended.

Otherwise, it replaces an existing tail with a smaller value. This keeps future extension opportunities as flexible as possible.

Finally, the size of lis is returned as the answer.

Go Solution

package main

import (
	"sort"
)

func maxEnvelopes(envelopes [][]int) int {
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] > envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})

	lis := []int{}

	for _, envelope := range envelopes {
		height := envelope[1]

		position := sort.Search(len(lis), func(i int) bool {
			return lis[i] >= height
		})

		if position == len(lis) {
			lis = append(lis, height)
		} else {
			lis[position] = height
		}
	}

	return len(lis)
}

The Go implementation follows the same logic as the Python solution.

sort.Slice is used for the custom sorting rule. Equal widths are sorted by descending height.

Go does not have a built in bisect_left function like Python, so sort.Search is used to perform binary search manually. The search finds the first index where the stored LIS tail is greater than or equal to the current height.

Slices in Go dynamically resize as needed, so appending new LIS values is straightforward.

There are no integer overflow concerns because envelope dimensions are at most 10^5, well within Go's standard integer range.

Worked Examples

Example 1

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

Step 1: Sort the envelopes

Sorting by width ascending and height descending gives:

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

Step 2: Extract heights

[3,4,7,4]

Step 3: Build LIS

Height	Binary Search Position	LIS After Processing
3	0	[3]
4	1	[3,4]
7	2	[3,4,7]
4	1	[3,4,7]

Final LIS length:

3

Valid nesting chain:

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

Example 2

Input: [[1,1],[1,1],[1,1]]

Step 1: Sort the envelopes

[[1,1],[1,1],[1,1]]

Step 2: Extract heights

[1,1,1]

Step 3: Build LIS

Height	Binary Search Position	LIS After Processing
1	0	[1]
1	0	[1]
1	0	[1]

Final LIS length:

1

Equal widths prevent nesting, so only one envelope can be chosen.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), and each LIS update uses binary search
Space	O(n)	The LIS array may store up to n heights

The dominant cost comes from sorting the envelopes. After sorting, each envelope participates in one binary search operation on the LIS array, which takes logarithmic time.

The auxiliary space comes from storing the LIS tails array, whose size can grow up to the number of envelopes.

Test Cases

from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        from bisect import bisect_left

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

        lis = []

        for _, height in envelopes:
            position = bisect_left(lis, height)

            if position == len(lis):
                lis.append(height)
            else:
                lis[position] = height

        return len(lis)

solution = Solution()

assert solution.maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]) == 3  # Basic example
assert solution.maxEnvelopes([[1,1],[1,1],[1,1]]) == 1  # All identical
assert solution.maxEnvelopes([[1,1]]) == 1  # Single envelope
assert solution.maxEnvelopes([[1,2],[2,3],[3,4],[4,5]]) == 4  # Fully increasing
assert solution.maxEnvelopes([[4,5],[4,6],[4,7]]) == 1  # Same width only
assert solution.maxEnvelopes([[5,4],[6,4],[6,5]]) == 2  # Equal widths edge case
assert solution.maxEnvelopes([[2,3],[5,4],[6,7],[6,8],[7,9]]) == 4  # Larger chain
assert solution.maxEnvelopes([[10,8],[1,12],[6,15],[2,18]]) == 2  # Mixed ordering
assert solution.maxEnvelopes([[1,10],[2,9],[3,8],[4,7]]) == 1  # Heights decreasing
assert solution.maxEnvelopes([[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]) == 5  # Complex LIS case

Test	Why
[[5,4],[6,4],[6,7],[2,3]]	Validates the main example
[[1,1],[1,1],[1,1]]	Ensures equal envelopes do not nest
[[1,1]]	Tests minimum input size
Strictly increasing sequence	Confirms maximum chain behavior
Same width envelopes	Ensures equal widths cannot nest
Equal width edge case	Verifies descending height sort correctness
Larger mixed chain	Tests longer valid subsequences
Random ordering	Confirms sorting logic works
Decreasing heights	Ensures LIS correctly rejects invalid chains
Complex LIS example	Stress tests binary search replacement behavior

Edge Cases

One important edge case occurs when multiple envelopes have the same width. Since nesting requires strictly increasing widths, envelopes with identical widths must never appear together in the final chain. A naive LIS approach on heights can mistakenly allow this. The descending height sort prevents that issue by ensuring equal width envelopes cannot form an increasing height subsequence.

Another important case is when all envelopes are identical. For example:

[[1,1],[1,1],[1,1]]

Every envelope has the same width and height, so no nesting is possible. The LIS algorithm correctly replaces the same position repeatedly instead of extending the sequence, resulting in an answer of 1.

A third critical case is when widths increase but heights decrease:

[[1,10],[2,9],[3,8],[4,7]]

Although widths are valid for nesting, heights are not strictly increasing. The LIS algorithm correctly identifies that only one envelope can be selected because every new height replaces the first LIS position instead of extending the subsequence.

Another subtle case occurs when the optimal sequence is not contiguous after sorting. The LIS approach naturally handles this because it searches globally for the best subsequence rather than greedily taking every possible envelope. This is why the binary search optimization is both efficient and correct.