Russian Doll Envelopes: A Dynamic Programming Interview Walkthrough
- 20 hours ago
- 10 min read
Russian Doll Envelopes is a dynamic programming problem that interviewers love because it tests whether you can recognize a familiar problem hiding inside an unfamiliar one. The challenge is in realizing that with the right sort, the second dimension collapses into a classic Longest Increasing Subsequence problem. That recognition is the actual signal the interviewer is looking for.
The same reduction pattern shows up in scheduling problems (jobs with two resource constraints), bin-fitting and container optimization (objects with multi-dimensional sizes), and any system where you're trying to find the longest chain of items under multiple ordering constraints, like resume screening with multiple monotonic filters or staircase-shaped data structures in computational geometry.
Problem Statement
You are given a list of envelopes, where each envelope is described by two integers [w, h] representing its width and height.
One envelope can fit into another if and only if both the width and height of one envelope are strictly less than the other.
Return the maximum number of envelopes you can nest (Russian doll) inside each other.
Example:
envelopes = [[5,4], [6,4], [6,7], [2,3]]
answer → 3 (the chain [2,3] → [5,4] → [6,7]).
1. Clarify Requirements Before Jumping Into Code
Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that may impact our approach.
Input:
a list of integer pairs [w, h].
Output: an integer - the maximum number of envelopes that can be nested.
Details to clarify:
Does "fit inside" require strict inequality on both dimensions? Yes, equal width or equal height means they can't nest.
Can envelopes be rotated? No, width is width and height is height.
Do we return the count or the actual chain? Just the count.
Can the input be empty? Yes - return 0 in that case.
Can dimensions be negative or zero? Assume positive integers unless told otherwise.
2. Identify the Category of the Question
A few signals jump out:
We're looking for the longest chain of items under an ordering constraint.
The ordering involves two dimensions, both of which need to be strictly increasing.
The items don't come with any natural order. We get to choose which subset to nest and in what arrangement.
That combination - longest chain, ordering constraint, arbitrary subset selection - is the fingerprint of Longest Increasing Subsequence. The catch is that LIS is normally a 1D problem (find the longest strictly increasing subsequence of an array), and here we have two dimensions to satisfy simultaneously. So our first instinct should be: is there a way to reduce this to LIS? That's the question driving the rest of the brainstorm.
3. Brute Force Solution
As always, we start with the brute force. The most direct approach is to try every subset of envelopes, check if each subset forms a valid nesting chain (after sorting), and track the longest valid chain.
for each subset of envelopes:
sort the subset by width
check if heights and widths both strictly increase
if valid, update maxThat's O(2^n) just for enumerating subsets, plus O(n log n) per subset to verify. We should be able to do better than that.
A slightly smarter brute force would skip the subset enumeration and use the standard O(n²) LIS DP - for each envelope, look at every earlier envelope and check if it nests. We'll come back to that. The takeaway from the brute force is that the problem really is about finding a chain, and the chain has to respect an ordering on both dimensions at once.
4. Brainstorm More Solutions
Step 1: How would we approach this manually?
Let's think about how we would solve [[5,4], [6,4], [6,7], [2,3]] by hand.
The first thing I'd do is sort the envelopes somehow, because nesting is fundamentally about ordering. The outer envelope must come "after" the inner one in both width and height. Without any ordering, I'd be checking all pairs against each other, and that's the brute force solution.
So let's sort by width ascending: [[2,3], [5,4], [6,4], [6,7]]. Now we can focus strictly on height and try to build the longest chain possible:
Start with [2,3]. Chain: [[2,3]].
[5,4]: height 4 > 3 ✓. Chain: [[2,3], [5,4]].
[6,4]: height 4, not > 4. Skip.
[6,7]: height 7 > 4 ✓. Chain: [[2,3], [5,4], [6,7]].
Length 3. That matches the expected answer.
This is promising. Once the envelopes are sorted by width, the width constraint is mostly taken care of (envelopes earlier in the list have width ≤ later envelopes). The only thing left to enforce is strictly increasing height - which is exactly LIS on the height column.
But before we jump into coding, we should pause to think through potential edge cases. For example, what happens if there are widths that have the same value?
Step 2: Find the trap with equal widths
Let's try a different input: [[4,5], [4,6], [4,7]]. All three envelopes have width 4. None of them can nest, because the widths aren't strictly increasing - they're equal. So, the correct answer is 1.
But what happens if I sort by width ascending and then run LIS on the heights?
After sorting (width is tied, so order among them is arbitrary): [[4,5], [4,6], [4,7]]. Heights: [5, 6, 7]. Now LIS gives us a length of 3.
That's answer is incorrect. The algorithm thinks all three can nest, because the heights are strictly increasing, but that breaks one of our constraints - the widths are equal, so none of them satisfies the strict inequality on width.
The bug is that sorting by width ascending lets envelopes with equal widths sit next to each other in increasing height order, which then looks like a valid chain to LIS. We need to find a way to prevent that.
Step 3: Fix the sort to disarm the trap
We only need one envelope of width x in my LIS. So, when two envelopes have the same width, we need to ensure they can't both appear in the same LIS. Since the only other variable we can work with here is height, what can we do with height to guarantee that only one of them appears in my LIS? We sort them by height in descending order when widths are equal!
So the rule becomes: sort by width ascending; on ties, sort by height descending.
Let's see what that does to [[4,5], [4,6], [4,7]].
After sorting: [[4,7], [4,6], [4,5]].
Heights: [7, 6, 5]. LIS length on a strictly decreasing sequence: 1. ✓
Why does this work? Within a group of envelopes that share a width, heights now appear in decreasing order. LIS requires strictly increasing values, so it can pick at most one envelope from any equal-width group. That's exactly what we want - equal widths can't nest, so we should only ever take one.
Meanwhile, between groups of different widths, the heights aren't constrained to any pattern. LIS will pick whichever heights form the longest increasing chain across groups. The width constraint is automatically satisfied because we sorted ascending by width.
This is the move that makes the whole reduction work. Without the descending tiebreaker, the 2D problem doesn't cleanly collapse to 1D. With it, the algorithm is just "sort, then LIS."
Step 4: O(n²) DP on heights
Now that the reduction is solid, let's start with the straightforward LIS solution. Review it here if you want a deep dive into how to build up that solution from scratch.
After sorting, let dp[i] be the length of the longest valid nesting chain ending at envelope i. The transition is:
dp[i] = 1 + max(dp[j]) for all j < i where heights[j] < heights[i]
(or 1 if no such j exists)We initialize each dp[i] = 1 (every envelope is at least a chain of length 1 by itself) and return the max over all dp[i].
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) return b[1] - a[1];
return a[0] - b[0];
});
int n = envelopes.length;
int[] dp = new int[n];
int best = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (envelopes[j][1] < envelopes[i][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]);
}
return best;
}That's O(n²) time, O(n) space. Correct, simple, and a reasonable answer in an interview if you can't remember the O(n log n) trick. But for large inputs (n in the tens of thousands), it'll time out. So let's think about how we could optimize.
Step 5: Optimize to O(n log n) with the patience-sort trick
The standard O(n log n) LIS algorithm uses a clever idea sometimes called patience sorting. Instead of computing dp[i] for every position, we maintain an array tails, where tails[k] holds the smallest possible ending value of any increasing subsequence of length k + 1 we've seen so far.
Our array tails[k] then represents the best possible "starting platform" for a future extension. Keeping it as small as possible at each length means we have the most room to grow.
The full correctness proof is by induction on the length of the array, but the intuition is enough for an interview.
Tails is always sorted in increasing order, so for each new height h, we can use binary search to find where h fits:
If h is greater than every value in tails, it extends the longest subsequence, so we append it to tails.
Otherwise, we find the smallest value in tails that is ≥ h and replace it with h. The ≥ here is important because we want a strictly increasing subsequence.This doesn't change the length of any existing subsequence, but it lowers the ending value of length-k subsequences, which gives future heights a better chance of extending them.
At the end, the length of tails is the LIS length.
Here's the implementation:
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) return 0;
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) return b[1] - a[1];
return a[0] - b[0];
});
int[] tails = new int[envelopes.length];
int size = 0;
for (int[] env : envelopes) {
int h = env[1];
// Binary search for the first index in tails[0..size) with tails[index] >= h
int left = 0, right = size;
while (left < right) {
int mid = (left + right) / 2;
if (tails[mid] < h) left = mid + 1;
else right = mid;
}
tails[left] = h;
if (left == size) size++;
}
return size;
}The sort is O(n log n). The LIS pass is O(n log n) - n heights, each processed with one binary search of size up to n. Total: O(n log n), with O(n) space for tails.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Brute-force subset enumeration | O(2^n × n) | O(n) | Never, but worth mentioning to frame the problem |
Sort + O(n²) LIS DP | O(n²) | O(n) | If I can't recall the patience-sort trick, this is correct and easy to write |
Sort + O(n log n) LIS | O(n log n) | O(n) | My default interview answer, what interviewers expect for full credit |
The O(n²) version is worth knowing as a fallback. It's much easier to write correctly under pressure, and it runs fine for moderate input sizes. The O(n log n) version is the polished answer, but the patience-sort trick requires explanation, and writing the binary search correctly under pressure can be tricky.
6. Pseudocode
if envelopes is empty: return 0
sort envelopes:
primary key: width ascending
tie-breaker: height descending
tails = empty array
for each envelope (w, h) in sorted order:
use binary search to find the first index i in tails where tails[i] >= h
if i == length(tails):
append h to tails
else:
tails[i] = h
return length of tails7. Edge Cases
Things to verify before claiming we're done:
Empty input → return 0. Handled by the early return.
All envelopes identical → after sorting, all heights are identical. Each one replaces the same slot in tails. Final size: 1. ✓
All envelopes share a width but have different heights → the descending tiebreaker means heights appear in strictly decreasing order, so LIS picks only one. ✓
All envelopes share a height but have different widths → heights are all equal, so LIS picks only one. ✓
A perfect nesting chain → each envelope extends tails by one. Size grows to n. ✓
Reversed nesting chain → each envelope replaces the first slot in tails. Size stays at 1. ✓
The width-asc / height-desc sort is what makes the equal-width case work without special-casing. That tiebreaker is doing real work, not just being clever.
8. Full Code
import java.util.*;
public class RussianDollEnvelopes {
public static int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
// Sort by width ascending; on equal widths, sort by height descending.
// The descending tiebreaker prevents equal-width envelopes from forming a chain in the LIS step.
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) return b[1] - a[1];
return a[0] - b[0];
});
int[] tails = new int[envelopes.length];
int size = 0;
for (int[] env : envelopes) {
int h = env[1];
// Binary search for the first index where tails[index] >= h.
// Using >= (not >) keeps the LIS strictly increasing.
int left = 0, right = size;
while (left < right) {
int mid = (left + right) / 2;
if (tails[mid] < h) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = h;
if (left == size) {
size++;
}
}
return size;
}
}9. Test the Code
System.out.println(maxEnvelopes(new int[][]{{5,4},{6,4},{6,7},{2,3}})); // 3
System.out.println(maxEnvelopes(new int[][]{{1,1},{1,1},{1,1}})); // 1
System.out.println(maxEnvelopes(new int[][]{})); // 0
System.out.println(maxEnvelopes(new int[][]{{4,5},{4,6},{4,7}})); // 1
System.out.println(maxEnvelopes(new int[][]{{1,2},{2,3},{3,4},{4,5}})); // 4
System.out.println(maxEnvelopes(new int[][]{{5,4},{4,5}})); // 1These hit the meaningful cases: the canonical example, all duplicates, empty input, equal widths with different heights, a perfectly nestable chain, and the tricky "swap" case where each envelope is bigger in one dimension and smaller in the other.
10. Key Lessons
When a problem has two ordering constraints, try sorting on one of them. If the sort fully encodes that constraint, the problem collapses to one dimension on the other constraint. This pattern shows up far beyond LIS variants.
The sort's tiebreaker often does more work than the primary key. The descending tiebreaker here is what makes the reduction sound. Whenever you're sorting to collapse a problem, think carefully about what happens to equal values.
Recognize when a problem has another problem hiding inside it. Russian Doll Envelopes isn't really about envelopes - it's about LIS with a preprocessing step. A lot of interview problems are "do thing X, then run a classical algorithm Y." Spotting Y is half the battle.
O(n log n) LIS via patience sorting is worth memorizing as a standalone tool. It comes up in LIS itself, in this problem, in "longest chain of pairs," and in several scheduling problems.
Strict vs. non-strict inequality matters everywhere - in the original problem statement, in the sort comparator, and in the binary search condition. One wrong choice cascades into a wrong answer that passes most tests but fails on duplicates.
The thing that makes Russian Doll Envelopes click isn't the LIS algorithm - most candidates know LIS. It's the willingness to look at a 2D problem and ask whether the right preprocessing can make one of the dimensions disappear. Once you see that move, a whole family of multi-constraint optimization problems starts to look familiar.
Good Luck and Happy Coding!
Comments