252. Russian Doll Envelopes
🔗 LeetCode Problem: 354. Russian Doll Envelopes
📊 Difficulty: Hard
🏷️ Topics: Array, Binary Search, Dynamic Programming, Sorting, DP - LIS
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 <= 10^5
- envelopes[i].length == 2
- 1 <= wi, hi <= 10^5
🧒 Starting From Zero
What Does "Russian Doll" Mean?
Real-life Russian dolls (Matryoshka):
🪆 Tiny
🪆🪆 Small (tiny fits inside)
🪆🪆🪆 Medium (small fits inside)
🪆🪆🪆🪆 Large (medium fits inside)
Each doll fits COMPLETELY inside the next!
For envelopes:
Envelope A fits inside Envelope B if:
A's width < B's width AND
A's height < B's height
BOTH dimensions must be strictly smaller! 🔑
Simple Example
envelopes = [[2,3], [5,4], [6,4], [6,7]]
Can [2,3] fit inside [5,4]?
Width: 2 < 5? YES! ✓
Height: 3 < 4? YES! ✓
Can fit! ✓
Can [5,4] fit inside [6,4]?
Width: 5 < 6? YES! ✓
Height: 4 < 4? NO! EQUAL! ✗
Can't fit! ✗
Can [5,4] fit inside [6,7]?
Width: 5 < 6? YES! ✓
Height: 4 < 7? YES! ✓
Can fit! ✓
Longest chain: [2,3] → [5,4] → [6,7] = 3 envelopes! ✓
This Looks Like LIS!
Regular LIS (1D):
Array: [10, 9, 2, 5, 3, 7]
Condition: nums[j] < nums[i]
Compare ONE dimension!
Russian Doll (2D):
Envelopes: [[2,3], [5,4], [6,7]]
Condition: w[j] < w[i] AND h[j] < h[i]
Compare TWO dimensions!
Same pattern, but 2D! 🔑
🤔 Building Understanding
Approach 1: Straightforward 2D DP
Most natural solution:
dp[i] = longest chain ending at envelope i
For each envelope i:
For each j < i:
If env[j] fits in env[i]:
dp[i] = max(dp[i], dp[j] + 1)
Check: width[j] < width[i] AND height[j] < height[i]
This works! Time: O(n²)
For n = 10^5: 10 billion comparisons ✗
Too slow!
Can we optimize?
The Key Insight - Sort First!
For regular 1D LIS:
We don't need to check ALL previous elements
If we process in order, we build up solution
For 2D envelopes:
Can we create an order?
Idea: Sort by one dimension!
If we sort by WIDTH:
[[2,3], [5,4], [6,4], [6,7]]
Width constraint becomes easier!
Earlier envelopes have smaller/equal width
We only need to check HEIGHT! 🔑
Reducing 2D to 1D
After sorting by width:
[[2,3], [5,4], [6,4], [6,7]]
Widths: [2, 5, 6, 6]
Width constraint:
For j < i: width[j] ≤ width[i] (due to sort)
So our check simplifies:
OLD: width[j] < width[i] AND height[j] < height[i]
NEW: Just check height[j] < height[i]
(width already handled by sort order!)
Extract heights: [3, 4, 4, 7]
Find LIS of heights!
This reduces 2D problem to 1D LIS! ✓
⚠️ The Critical Problem
What Goes Wrong?
Let's try our idea:
envelopes = [[1,3], [3,4], [3,5], [6,7]]
Sort by width:
[[1,3], [3,4], [3,5], [6,7]]
Extract heights: [3, 4, 5, 7]
Find LIS of [3, 4, 5, 7]:
All increasing!
LIS = [3, 4, 5, 7]
Length = 4!
Is this correct?
Let's Verify
LIS picked all 4 envelopes:
[1,3], [3,4], [3,5], [6,7]
Can they nest?
[1,3] → [3,4]: width 1<3? YES, height 3<4? YES ✓
[3,4] → [3,5]: width 3<3? NO! SAME WIDTH! ✗
WRONG! ✗
The problem:
[3,4] and [3,5] both have width 3
They CAN'T nest inside each other!
But LIS picked BOTH!
Why?
LIS only looks at HEIGHTS: [3, 4, 5, 7]
It sees: 3 < 4 < 5 < 7
It doesn't know [3,4] and [3,5] have same width!
We LOST width information when we extracted heights! 🔑
The Core Issue
After sorting and extracting heights:
We're doing LIS on HEIGHTS ONLY
LIS algorithm sees: [3, 4, 5, 7]
It thinks:
"4 < 5? Yes! I can extend!"
But envelopes [3,4] and [3,5]:
width 3 == 3 ✗
CAN'T nest!
Problem:
Same-width envelopes can pick AT MOST ONE
But LIS on heights doesn't know which have same width!
How do we fix this? 🤔
💡 The Brilliant Solution
The Fix - Height Descending for Same Width!
KEY INSIGHT:
For envelopes with SAME width:
- They can NEVER nest (width must be strictly less)
- We can pick AT MOST ONE for our chain
Problem:
LIS on heights doesn't know which have same width
Solution:
Make their heights DECREASE!
Why?
Decreasing heights can't be in same LIS!
LIS picks increasing sequences!
Example: Heights [5, 4, 3] (all same width)
LIS can pick: [5] OR [4] OR [3]
But NOT [5,4] or [4,3] (not increasing!)
At most ONE picked! ✓
Applying The Fix
Same example: [[1,3], [3,4], [3,5], [6,7]]
OLD sort (width↑, height↑):
[[1,3], [3,4], [3,5], [6,7]]
Heights: [3, 4, 5, 7]
LIS picks all 4 ✗
NEW sort (width↑, height↓ for same width):
Step 1: Sort by width
Step 2: For SAME width, sort height DESCENDING
[[1,3], [3,5], [3,4], [6,7]]
↑ ↑
Width 3, but 5 > 4 (descending!)
Heights: [3, 5, 4, 7]
Find LIS of [3, 5, 4, 7]:
i=0: 3, dp=1
i=1: 5>3? YES, dp=2
i=2: 4>5? NO! 4>3? YES, dp=2
i=3: 7>4? YES, dp=3
Maximum = 3 ✓
Which envelopes?
Sequence with heights [3, 5, 7]: [1,3]→[3,5]→[6,7] ✓
OR sequence [3, 4, 7]: [1,3]→[3,4]→[6,7] ✓
Both valid! Both length 3!
The key:
LIS picked either [5,7] or [4,7]
But NOT [5,4,7] (since 5>4, not increasing)
It automatically avoided picking BOTH [3,5] and [3,4]! ✓
Why It Works - The Complete Understanding
After sorting width↑, height↓:
For envelopes with DIFFERENT widths:
- Width increases naturally (sorted)
- Heights can increase, decrease, whatever
- LIS handles height constraint ✓
For envelopes with SAME width:
- Heights are DECREASING
- LIS sees: [5, 4] (decreasing)
- Can't both be in LIS! (needs increasing)
- Picks at most ONE! ✓
Result:
Width constraint: handled by sorting
Same-width limit: handled by descending heights
Height constraint: handled by LIS
All constraints satisfied! ✓
🎯 Complete Solutions
Approach 1: Brute Force - Try All Chains (DFS)
The Naive Idea:
Try every possible chain:
1. Start from each envelope
2. For each, try adding any other envelope that fits
3. Recursively explore all possibilities
4. Track maximum length
Complete Implementation:
class Solution {
private int maxChain = 0;
public int maxEnvelopes(int[][] envelopes) {
// Try starting from each envelope
boolean[] used = new boolean[envelopes.length];
for (int i = 0; i < envelopes.length; i++) {
used[i] = true;
dfs(envelopes, i, 1, used);
used[i] = false;
}
return maxChain;
}
private void dfs(int[][] envelopes, int current, int length, boolean[] used) {
maxChain = Math.max(maxChain, length);
int[] curr = envelopes[current];
// Try extending with each unused envelope
for (int i = 0; i < envelopes.length; i++) {
if (used[i]) continue;
int[] next = envelopes[i];
// Can current fit inside next?
if (curr[0] < next[0] && curr[1] < next[1]) {
used[i] = true;
dfs(envelopes, i, length + 1, used);
used[i] = false;
}
}
}
}
Example Trace:
envelopes = [[5,4], [6,4], [6,7], [2,3]]
Start from [5,4]:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try [6,4]: 5<6? YES, 4<4? NO ✗
Try [6,7]: 5<6? YES, 4<7? YES ✓
Chain: [5,4] → [6,7], length=2
Try extending [6,7]...
No more fit!
Try [2,3]: 5<2? NO ✗
Start from [6,4]:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try [5,4]: 6<5? NO ✗
Try [6,7]: 6<6? NO ✗
Try [2,3]: 6<2? NO ✗
Chain: [6,4], length=1
Start from [6,7]:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try [5,4]: 6<5? NO ✗
Try [6,4]: 6<6? NO ✗
Try [2,3]: 6<2? NO ✗
Chain: [6,7], length=1
Start from [2,3]:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try [5,4]: 2<5? YES, 3<4? YES ✓
Chain: [2,3] → [5,4]
From [5,4], try [6,7]: 5<6? YES, 4<7? YES ✓
Chain: [2,3] → [5,4] → [6,7], length=3 ✓
Try [6,4]: 2<6? YES, 3<4? YES ✓
Chain: [2,3] → [6,4]
From [6,4], try [6,7]: 6<6? NO ✗
Try [6,7]: 2<6? YES, 3<7? YES ✓
Chain: [2,3] → [6,7], length=2
Maximum: 3 ✓
Why This Is Too Slow:
TIME: O(n! × n)
For each starting envelope: O(n) choices
For each next: O(n-1) choices
And so on...
Factorial possibilities!
Each path: check O(n) envelopes
For n = 10^5:
WAY TOO SLOW! ✗
SPACE: O(n)
Recursion stack depth
Boolean array
This is correct but IMPRACTICAL!
Need optimization → DP!
What We Learn:
Brute force shows:
1. Problem is about finding longest chain
2. Many overlapping subproblems
(same envelope reached via different paths)
3. Checking all pairs is expensive
These observations lead us to DP! 🔑
Approach 2: Standard DP - O(n²)
class Solution {
public int maxEnvelopes(int[][] envelopes) {
// Sort: width ascending, height descending for same width
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1]; // Descending height
}
return a[0] - b[0]; // Ascending width
});
// Extract heights
int n = envelopes.length;
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = envelopes[i][1];
}
// Standard LIS on heights
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (heights[j] < heights[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
Why We Only Check Heights:
After sorting by width, why do we only check:
if (heights[j] < heights[i])
Instead of:
if (widths[j] < widths[i] && heights[j] < heights[i])
Reason:
1. For j < i in sorted array:
widths[j] ≤ widths[i] (guaranteed by sort)
2. If widths[j] == widths[i]:
Heights are descending!
heights[j] > heights[i]
So heights[j] < heights[i] is FALSE ✓
We DON'T extend! (correct!)
3. If widths[j] < widths[i]:
Just check heights[j] < heights[i]
If true, we can extend! ✓
The descending height for same width ensures:
Same-width envelopes automatically fail the height check! 🔑
Complexity:
TIME: O(n²)
Sort: O(n log n)
LIS DP: O(n²)
SPACE: O(n)
For n = 10^5: Still too slow! ✗
Approach 3: Binary Search LIS - O(n log n) OPTIMAL
The Optimization:
Standard LIS: O(n²)
Binary Search LIS: O(n log n)!
From Problem 247, we learned:
LIS can be found faster using binary search!
Idea:
Maintain "tails" array
tails[i] = smallest ending value for LIS of length i+1
For each element:
Binary search where it fits
Update or extend tails
This is faster! 🚀
Complete Implementation:
class Solution {
public int maxEnvelopes(int[][] envelopes) {
// Sort: width ascending, height descending for same width
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
// Extract heights
int n = envelopes.length;
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = envelopes[i][1];
}
// LIS with binary search
return lengthOfLIS(heights);
}
private int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
tails.add(num);
} else {
tails.set(pos, num);
}
}
return tails.size();
}
private int binarySearch(List<Integer> tails, int target) {
int left = 0, right = tails.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
How Binary Search LIS Works:
Example: [3, 5, 4, 7]
tails array: stores smallest tail for each LIS length
Process 3:
tails = [3]
Process 5:
5 > 3, extend!
tails = [3, 5]
Process 4:
Binary search: where does 4 fit?
tails[0]=3 < 4, tails[1]=5 > 4
Position = 1
Replace: tails[1] = 4
tails = [3, 4]
Why replace?
LIS length still 2
But tail=4 is better than tail=5
(more elements > 4 than > 5)
Process 7:
7 > 4, extend!
tails = [3, 4, 7]
Final length = 3 ✓
Complexity:
TIME: O(n log n)
Sort: O(n log n)
LIS: O(n log n)
SPACE: O(n)
For n = 10^5: ~1.6 million operations ✓
OPTIMAL! ✓
📊 Complete Example Trace
envelopes = [[5,4],[6,4],[6,7],[2,3]]
STEP 1: Sort width↑, height↓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Compare [5,4] vs [2,3]: width 5 vs 2 → [2,3] first
Compare [6,4] vs [6,7]: same width, height 4 vs 7 → [6,7] first!
After sort: [[2,3], [5,4], [6,7], [6,4]]
↑ ↑
Same width 6, descending heights!
STEP 2: Extract heights
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
heights = [3, 4, 7, 4]
STEP 3: Find LIS of heights
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Standard DP:
i=0: height=3
dp[0] = 1
i=1: height=4
4 > 3? YES!
dp[1] = dp[0] + 1 = 2
i=2: height=7
7 > 3? YES, dp=2
7 > 4? YES, dp=3
dp[2] = 3
i=3: height=4
4 > 3? YES, dp=2
4 > 4? NO
4 > 7? NO
dp[3] = 2
Final: dp = [1, 2, 3, 2]
Maximum: 3 ✓
The chain:
Heights [3, 4, 7]
Envelopes: [[2,3], [5,4], [6,7]]
Verify:
[2,3] → [5,4]: 2<5, 3<4 ✓
[5,4] → [6,7]: 5<6, 4<7 ✓
CORRECT! ✓
Note: We didn't pick [6,4] even though it's in array!
Why? Its height=4 is same as [5,4]
Can't extend 4→4 (need strictly increasing)
✓
🔑 Key Insights
The Core Understanding
1. SORT BY WIDTH:
Reduces 2D problem to 1D
Width constraint handled by order
2. HEIGHT DESCENDING FOR SAME WIDTH:
Prevents LIS from picking multiple same-width envelopes
Same width → heights decrease
Decreasing → can't both be in LIS
At most one picked! ✓
3. LIS ON HEIGHTS:
Handles height constraint
Works on extracted height array
All three pieces together solve the problem! 🔑
Why This Is Brilliant
Original problem:
2D constraint (width AND height)
O(n²) DP needed
After transformation:
1D LIS problem!
O(n log n) possible!
The sorting trick:
Handles one dimension completely
Transforms to standard LIS
Genius! ✨
Common Misconceptions
WRONG: "We check both width and height in DP"
RIGHT: We only check heights! Width handled by sort!
WRONG: "Descending height is arbitrary"
RIGHT: It's critical! Prevents picking multiple same-width!
WRONG: "Binary search is complicated"
RIGHT: It's standard LIS binary search (from Problem 247)!
📝 Quick Revision
🎯 Core Algorithm
1. Sort envelopes:
- Primary: width ascending
- Secondary: height DESCENDING (same width only!)
2. Extract heights array
3. Find LIS of heights (binary search)
4. Return LIS length
🔑 Why It Works
After sorting:
- Width constraint: automatic (sort order)
- Same-width limit: descending prevents picking both
- Height constraint: LIS handles it
Reduces 2D → 1D! ✓
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class Solution {
int maxLen = 0;
public int maxEnvelopes(int[][] a) {
maxLen = 0;
// return dfs(a); // bruteforce
// return dfsWithSort(a);
// return dpWithWidSorted(a);
// return dpWithWidAndHeightSorted(a);
return bs(a);
}
private int bs(int[][] envelopes) {
// step 1: sort by width first. If widths are same, sort by heights (descending)
Arrays.sort(envelopes, (e1, e2) -> {
if (e1[0] == e2[0]) {
return e2[1] - e1[1];
} else {
return e1[0] - e2[0];
}
});
// step 2: take heights alone
int len = envelopes.length;
int[] a = new int[len];
for (int i = 0; i < len; i++) {
a[i] = envelopes[i][1];
}
// step 3: same as regular LIS with binary search
// Above DP with width and heights are enough. We are coming here only to handle
// 2 large test cases
List<Integer> tails = new ArrayList<>();
for (int num : a) {
// Binary search for position
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
// Create new pile (means incoming number is
// greater than all the current elements of the list)
tails.add(num);
} else {
// Replace pile top
tails.set(pos, num);
}
}
return tails.size();
}
// returns position (leftmost) where tails[pos] >= num
private int binarySearch(List<Integer> tails, int num) {
int left = 0;
int right = tails.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < num) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int dpWithWidAndHeightSorted(int[][] a) {
// step 1: sort by width first. If widths are same, sort by heights (descending)
Arrays.sort(a, (e1, e2) -> {
if (e1[0] == e2[0]) {
return e2[1] - e1[1];
} else {
return e1[0] - e2[0];
}
});
int len = a.length;
int res = 1;
int[] dp = new int[len];
// step 2: from here, same as earlier DP LIS problems with condition changed
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (a[j][0] < a[i][0] && a[j][1] < a[i][1]) {
dp[i] = Math.max(dp[i], 1 + dp[j]);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
private int dpWithWidSorted(int[][] a) {
// step 1: sort by width only.
Arrays.sort(a, (e1, e2) -> {
return e1[0] - e2[0];
});
int len = a.length;
int res = 1;
int[] dp = new int[len];
// step 2: from here, same as earlier DP LIS problems with condition changed
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (a[j][0] < a[i][0] && a[j][1] < a[i][1]) {
dp[i] = Math.max(dp[i], 1 + dp[j]);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
private int dfsWithSort(int[][] a) {
// step 1: sort by width first. If widths are same, sort by heights
Arrays.sort(a, (e1, e2) -> {
if (e1[0] == e2[0]) {
return e1[1] - e2[1];
} else {
return e1[0] - e2[0];
}
});
// step 2: same as earlier approach. Now no need of used/visited array
int len = a.length;
for (int i = 0; i < len; i++) {
dfsUtilWithSort(a, i, 1);
}
return maxLen;
}
private void dfsUtilWithSort(int[][] a, int curr, int currChainLength) {
maxLen = Math.max(currChainLength, maxLen);
for (int i = curr + 1; i < a.length; i++) {
if (a[curr][0] < a[i][0] && a[curr][1] < a[i][1]) {
dfsUtilWithSort(a, i, currChainLength + 1);
}
}
}
private int dfs(int[][] a) {
int len = a.length;
boolean[] used = new boolean[len];
// step 1: start dfs from every envelope.
// mark it as visited to avoid duplicate includes
for (int i = 0; i < len; i++) {
used[i] = true;
dfsUtil(a, i, 1, used);
used[i] = false;
}
return maxLen;
}
private void dfsUtil(int[][] a, int curr, int currChainLength, boolean[] used) {
maxLen = Math.max(currChainLength, maxLen);
for (int i = 0; i < a.length; i++) {
// Step 2: not using already used envelope
if (used[i]) {
continue;
}
// Step 3: curr < i (widths and heights), so that it can be enveloped
// if its can be enveloped with curr, proceed with next card.
if (a[curr][0] < a[i][0] && a[curr][1] < a[i][1]) {
used[i] = true;
dfsUtil(a, i, currChainLength + 1, used);
used[i] = false;
}
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.maxEnvelopes(new int[][] { { 5, 4 }, { 6, 4 }, { 6, 7 }, { 2, 3 } }) == 3);
System.out.println(s.maxEnvelopes(new int[][] { { 1, 1 }, { 1, 1 }, { 1, 1 } }) == 1);
}
}
⚡ Complexity
TIME: O(n log n)
SPACE: O(n)
OPTIMAL! ✓
🎉 Congratulations!
You've mastered: - ✅ 2D to 1D reduction - ✅ The descending height trick - ✅ Why we check only heights - ✅ Binary search LIS optimization - ✅ Complete understanding!
KEY TAKEAWAY: When you have multiple dimensions, sort by one dimension and reduce to 1D problem on the other! The sorting order matters - use it to encode constraints! 🔑🚀✨