354. Russian Doll Envelopes
Russian Doll Envelopes (LeetCode 354) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.
How to solve Russian Doll Envelopes
Russian Doll Envelopes is a Longest Increasing Subsequence problem, part of Dynamic Programming (DP) Patterns. Find LIS using DP and binary search optimization. O(n log n) solution.
Work towards the solution in these steps:
- Consider how sorting can help simplify the problem by imposing an order on the envelopes.
- Think about transforming the two-dimensional problem into a one-dimensional one after sorting.
- Recall the Longest Increasing Subsequence (LIS) pattern and how it can be applied to the heights once widths are sorted.
The reference solution runs in O(n log n) time and O(n) space.
The Russian Doll Envelopes solution and editorial walks through the full approach with reference code.
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
Topics and companies
Topics: Array, Binary Search, Dynamic Programming, Sorting.
Reported in interviews at Google, Amazon, ByteDance, Uber.
How to practise Russian Doll Envelopes on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(n) space.
Open Russian Doll Envelopes in the code editor, or read the Russian Doll Envelopes editorial for a worked solution with its approach and complexity analysis.
Where Russian Doll Envelopes sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- Longest Increasing Subsequence (LIS) subpattern
- The full DSA patterns sheet
Problems related to Russian Doll Envelopes
Other problems that use the same Longest Increasing Subsequence (LIS) and Dynamic Programming (DP) Patterns techniques:
- Longest Increasing Subsequence — Medium, same subpattern
- Longest Increasing Subsequence II — Hard, same subpattern
- Minimum Number of Removals to Make Mountain Array — Hard, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
Russian Doll Envelopes FAQ
What is the LeetCode number of Russian Doll Envelopes?
Russian Doll Envelopes is LeetCode problem 354, rated Hard.
What pattern is used to solve Russian Doll Envelopes?
Russian Doll Envelopes is a Longest Increasing Subsequence problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.
What is the time complexity of Russian Doll Envelopes?
The reference solution runs in O(n log n) time and O(n) space.
Which companies ask Russian Doll Envelopes?
Russian Doll Envelopes has been reported in interviews at Google, Amazon, ByteDance, Uber.