Skip to main content
Talentd

Russian Doll Envelopes - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingSorting7 min readAsked at: Amazon, Microsoft, Goldman Sachs +10
Practice this problem

Problem Statement

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

 

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

 

Constraints:

  • 1 <= envelopes.length <= 105
  • envelopes[i].length == 2
  • 1 <= wi, hi <= 105

Approach Overview

Problem Overview: You are given envelopes with width and height. One envelope can fit inside another only if both width and height are strictly larger. The task is to compute the maximum number of envelopes you can nest inside each other, similar to Russian dolls.

Approach 1: Dynamic Programming (O(n²) time, O(n) space)

Start by sorting envelopes by width in ascending order. If widths are equal, sort by height to keep ordering consistent. After sorting, the problem becomes similar to finding the longest increasing subsequence (LIS) based on envelope height while ensuring widths increase. Use a DP array where dp[i] stores the maximum number of envelopes ending with envelope i. Iterate through previous envelopes and update dp[i] when both width and height are increasing. This approach clearly demonstrates the relationship to dynamic programming, but the nested loop results in O(n²) time.

Approach 2: Binary Search Optimization (O(n log n) time, O(n) space)

The optimal solution converts the problem into a longest increasing subsequence on heights. First sort envelopes by width ascending, but when widths are equal sort heights in descending order. This trick prevents envelopes with the same width from being counted in the subsequence. After sorting, extract heights and compute LIS using a binary search technique. Maintain a list where each element represents the smallest possible tail for an increasing subsequence of a given length. For every height, use binary search to find the replacement position. This reduces the LIS computation to O(n log n). The method combines sorting, array traversal, and binary search to achieve optimal performance.

Recommended for interviews: The binary search LIS approach is the expected solution in most interviews because it improves the complexity from O(n²) to O(n log n). Still, explaining the DP formulation first shows that you understand the subsequence relationship before optimizing it with binary search.

Approach 1: Dynamic Programming Approach

In this approach, we first sort the envelopes by width and then by height in descending order (if widths are equal). This allows us to look for the longest increasing subsequence of the heights while ignoring the widths. We then use a dynamic programming array to keep track of the maximum sequence length found so far.

This Python solution sorts the envelopes, then iterates through them to find the longest increasing subsequence of heights using binary search from the bisect module.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n), where n is the number of envelopes, due to sorting and binary search operations.

Space Complexity: O(n) for the dp array.

Try this approach in the editor →

Approach 2: Binary Search Optimization

This approach involves sorting and using a binary search to optimize the search through the height for the longest increasing subsequence. This enhances efficiency over a simple dynamic programming solution due to reduced overhead from repeated searches.

This C++ solution involves sorting the envelopes and then using lower_bound to perform a binary search on the dp array, which stores the longest increasing subsequence of heights.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log n) because of sorting and binary search operations.

Space Complexity: O(n) to store the dp list.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n log n), where n is the number of envelopes, due to sorting and binary search operations.

Space Complexity: O(n) for the dp array.

Binary Search Optimization

Time Complexity: O(n log n) because of sorting and binary search operations.

Space Complexity: O(n) to store the dp list.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (LIS style)O(n²)O(n)Good for understanding the LIS relationship and when constraints are small.
Binary Search LIS OptimizationO(n log n)O(n)Preferred for large inputs and the standard optimal interview solution.

Video Solution

Russian Doll Envelopes | Dynamic Programming | Leetcode #354 | LIS • Techdose • 36,739 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Russian Doll Envelopes easy or hard?
Russian Doll Envelopes is categorized as a Hard problem because it requires recognizing the transformation to a Longest Increasing Subsequence problem and applying a sorting trick with binary search optimization.
Russian Doll Envelopes Python/Java solution
Implementations usually start by sorting envelopes and then computing the LIS of heights. Python and Java commonly use binary search (bisect in Python or Arrays.binarySearch logic in Java) to maintain the subsequence tails in O(n log n) time.
How to solve Russian Doll Envelopes in O(n log n)?
Sort envelopes by width ascending and height descending when widths are equal. Then run a Longest Increasing Subsequence algorithm on the heights array using binary search to maintain the smallest possible tail values for subsequences.
What is the best approach for Russian Doll Envelopes?
The optimal approach sorts envelopes by width ascending and height descending, then finds the Longest Increasing Subsequence (LIS) of heights using binary search. This reduces the complexity to O(n log n) and avoids counting envelopes with the same width.
Is Russian Doll Envelopes asked at Google/Amazon/Meta?
Russian Doll Envelopes is a classic LIS-based interview problem and has appeared in coding interviews at large tech companies including Google, Amazon, and Meta. It tests sorting strategy and subsequence optimization.
What data structure is used in Russian Doll Envelopes?
The optimal solution primarily uses arrays along with binary search to maintain the tails of increasing subsequences. Sorting and dynamic programming concepts are also involved.
What is the time complexity of Russian Doll Envelopes?
The optimal solution runs in O(n log n) time due to sorting and binary search operations during the LIS computation. A simpler dynamic programming approach exists with O(n²) time complexity and O(n) space.

Ready to solve this problem?

Practice Russian Doll Envelopes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Increasing Subsequence

Next

Longest Non-decreasing Subarray From Two Arrays