Log inSign up
hardLeetCodeNot Started

Russian Doll Envelopes

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

You are given a 2D array of integers envelopes where envelopes[i] = [w_i, h_i] 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 strictly 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 · 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 · Example 2:

Input: envelopes = [[1, 1], [1, 1], [1, 1]]
Output: 1
Explanation: Since widths and heights are equal, no envelope can fit inside another.

Constraints:

  • 1 <= envelopes.length <= 105
  • envelopes[i].length == 2
  • 1 <= w_i, h_i <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Russian Doll Envelopes.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Russian Doll Envelopes
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Small constraint sets (N <= 1000).
  • BETTER: Medium constraints where N <= 2500.
  • OPTIMAL: Optimal and necessary for N up to 105.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Recursion with Memoization / DFS on DAG

Intuition

Model each envelope as a node in a directed acyclic graph (DAG). Add a directed edge from envelope i to envelope j if w_i < w_j and h_i < h_j. Finding the maximum number of nested envelopes is equivalent to finding the length of the longest path in this DAG. Using depth-first search with memoization computes the answer, but constructing the graph or finding all paths takes O(n2) time and substantial recursion overhead, leading to Time Limit Exceeded when n = 105.

When to apply: Small constraint sets (N <= 1000).

Algorithm

  1. Step 1: Sort envelopes by width to guarantee an acyclic order.
  2. Step 2: Define a recursive function dfs(idx) returning the maximum chain ending or starting at envelope idx.
  3. Step 3: In dfs(idx), iterate through all j > idx. If envelopes[j] strictly contains envelopes[idx], recurse on j.
  4. Step 4: Memoize results in a memo array of size n.
  5. Step 5: Return 1 + maximum path length over all starting envelopes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int dfs(int idx, const std::vector<std::vector<int>>& env, std::vector<int>& memo) {
6 if (memo[idx] != -1) return memo[idx];
7 int maxChain = 1;
8 for (size_t next = idx + 1; next < env.size(); ++next) {
9 if (env[next][0] > env[idx][0] && env[next][1] > env[idx][1]) {
10 maxChain = std::max(maxChain, 1 + dfs(next, env, memo));
11 }
12 }
13 return memo[idx] = maxChain;
14}
15
16int maxEnvelopesBrute(std::vector<std::vector<int>>& envelopes) {
17 int n = envelopes.size();
18 if (n == 0) return 0;
19 std::sort(envelopes.begin(), envelopes.end());
20 std::vector<int> memo(n, -1);
21 int ans = 1;
22 for (int i = 0; i < n; ++i) {
23 ans = std::max(ans, dfs(i, envelopes, memo));
24 }
25 return ans;
26}
27
28int main() {
29 std::vector<std::vector<int>> envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
30 std::cout << maxEnvelopesBrute(envelopes) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(n^2) where n is the number of envelopes
  • Space complexity: O(n) auxiliary space for memoization table and call stack

2. Sort + 1D Dynamic Programming

Intuition

After sorting envelopes in ascending order: Define dp[i] as the maximum length of an envelope chain ending at envelope i. For each envelope i, check all previous envelopes j < i: If w_j < w_i and h_j < h_i, then envelope j fits strictly inside envelope i, so: $\text{dp}[i] = max(1, 1 + \text{dp}[j]) The result is \max_{0 <= i < n}(\text{dp}[i]). While intuitive and eliminating recursion, the double nested loop takes O(n2)$ time.

When to apply: Medium constraints where N <= 2500.

Algorithm

  1. Step 1: Sort envelopes primarily by width, secondarily by height in ascending order.
  2. Step 2: Allocate dp array of size n initialized to 1.
  3. Step 3: For each index i from 1 to n - 1, iterate j from 0 to i - 1.
  4. Step 4: If envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1], update dp[i] = max(dp[i], dp[j] + 1).
  5. Step 5: Return the maximum value found in dp.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maxEnvelopesDP(std::vector<std::vector<int>>& envelopes) {
6 int n = envelopes.size();
7 if (n == 0) return 0;
8 std::sort(envelopes.begin(), envelopes.end());
9 std::vector<int> dp(n, 1);
10 int ans = 1;
11 for (int i = 1; i < n; ++i) {
12 for (int j = 0; j < i; ++j) {
13 if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
14 dp[i] = std::max(dp[i], dp[j] + 1);
15 }
16 }
17 ans = std::max(ans, dp[i]);
18 }
19 return ans;
20}
21
22int main() {
23 std::vector<std::vector<int>> envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
24 std::cout << maxEnvelopesDP(envelopes) << std::endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n^2) time
  • Space complexity: O(n) auxiliary space for the dp array

3. Custom Sort (Width Ascending, Height Descending) + LIS via Binary Search

Intuition

To reduce the 2D problem to standard 1D LIS: 1. Key Insight: Sort envelopes primarily by width in ascending order (w_1 < w_2). If two envelopes have the same width, sort by height in descending order (h_1 > h_2). 2. Why descending height for equal widths? Two envelopes with equal widths cannot be nested inside each other. By sorting heights descending, when we run a strictly increasing subsequence check on heights, at most ONE envelope of each width can ever be selected! 3. Now, the problem reduces to finding the standard Longest Increasing Subsequence (LIS) on heights. 4. Using Patience Sorting (maintaining tails array with binary search / lower_bound), each height is inserted in O(log n) time. 5. Overall runtime drops to O(n log n), effortlessly handling n = 105.

When to apply: Optimal and necessary for N up to 105.

Algorithm

  1. Step 1: Sort envelopes: if a[0] != b[0] sort ascending by a[0]; otherwise sort descending by a[1].
  2. Step 2: Initialize an empty tails list to hold the smallest tail of all increasing subsequences of various lengths.
  3. Step 3: Iterate through each envelope [w, h], extracting h.
  4. Step 4: Use binary search (lower_bound) to locate the leftmost index in tails where tails[idx] >= h.
  5. Step 5: If no such element exists (idx == tails.length), append h to tails. Otherwise, replace tails[idx] = h.
  6. Step 6: Return tails.length as the length of the longest chain.

Interactive trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Sort envelopes by width asc, height desc: [[2, 3], [5, 4], [6, 7], [6, 4]]
Visual state
Values and pointers at this exact step
pointers
S
3
4
7
4
0
↑ currentIdx
1
2
3
Check / comparison
Sorted order established
Decision / next transition
Tails initialized to empty [].
Why this step matters

Sort envelopes by width asc, height desc: [[2, 3], [5, 4], [6, 7], [6, 4]]. Note: for width 6, height 7 comes before 4.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int maxEnvelopes(std::vector<std::vector<int>>& envelopes) {
6 if (envelopes.empty()) return 0;
7
8 std::sort(envelopes.begin(), envelopes.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
9 if (a[0] != b[0]) return a[0] < b[0];
10 return a[1] > b[1]; // descending on height for same width
11 });
12
13 std::vector<int> tails;
14 for (const auto& env : envelopes) {
15 int h = env[1];
16 auto it = std::lower_bound(tails.begin(), tails.end(), h);
17 if (it == tails.end()) {
18 tails.push_back(h);
19 } else {
20 *it = h;
21 }
22 }
23
24 return tails.size();
25}
26
27int main() {
28 std::vector<std::vector<int>> envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
29 std::cout << maxEnvelopes(envelopes) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n log n) time due to sorting and n binary searches
  • Space complexity: O(n) auxiliary space for the tails array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursion with Memoization / DFS on DAGO(n^2) where n is the number of envelopesO(n) auxiliary space for memoization table and call stackTreat envelopes as nodes in a DAG where a directed edge exists if envelope A fits strictly inside B. Find the longest path.O(n2) where n is the number of envelopes
2.Sort + 1D Dynamic ProgrammingO(n^2) timeO(n) auxiliary space for the dp arraySort envelopes by width and height ascending, then apply the classic O(n2) Longest Increasing Subsequence dynamic programming.O(n2) time
3.Custom Sort (Width Ascending, Height Descending) + LIS via Binary SearchOptimalO(n log n) time due to sorting and n binary searchesO(n) auxiliary space for the tails arraySort envelopes by width ascending and height descending. Then compute the Longest Increasing Subsequence on heights using binary search in O(n log n).O(n log n) time due to sorting and n binary searches

Common Pitfalls & Crucial Edge Cases

Sorting height ascending for equal widths

If equal widths have ascending heights, both could be picked in LIS, which violates the strict width nesting requirement w1 < w2.

Using non-strict inequality

An envelope must be strictly smaller in BOTH dimensions to fit inside another.

Using `upper_bound` instead of `lower_bound`

LIS requires strictly increasing heights, so lower_bound must be used to replace equal elements.

Crucial Edge Cases to Validate:

  • All envelopes have identical width — Because heights are sorted descending, only 1 envelope can be chosen.
  • All envelopes have identical height — Only 1 envelope can be chosen.
  • Single envelope — Maximum nesting is 1.
  • Large input (N = 10^5) — Solved in O(N log N) time.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the sorting insight brilliantly: 'Why do we sort heights descending for equal widths? To convert a 2D constraint into a 1D strictly increasing subsequence problem.'
  2. Explain the patience sorting mechanism and tails array invariant.
  3. Mention how this technique generalizes to multidimensional box stacking (Box Stacking, Cuboid Stacking).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How should envelopes [w, h] be sorted to reduce the problem to Longest Increasing Subsequence (LIS)?

2.After sorting, what algorithm finds the maximum nesting in O(N log N) time?

3.Why does the O(N2) DP approach fail on standard test suites?

Back to DSA Sheet