Russian Doll Envelopes
Problem
[w, h]. One envelope fits inside another only
if both its width and height are strictly smaller; envelopes cannot be
rotated. Return the maximum number of envelopes you can nest one inside another.[[5,4],[6,4],[6,7],[2,3]]Output3 ([2,3]→[5,4]→[6,7])[[1,1],[1,1],[1,1]]Output11 ≤ n ≤ 105 · 1 ≤ w, h ≤ 105
Try it yourself
class Solution {
public int maxEnvelopes(int[][] envelopes) {
}
}
Instinct Longest chain where each pick must beat the last (bigger, later, fits inside) - O(n²) best-ending-here DP, or O(n log n) tails plus binary search.
Memory hack Patience solitaire - drop each card on the leftmost pile whose top is not smaller; the number of piles is the LIS length.
Open the Longest Increasing Subsequence guide →Approaches
Brute ForceSort by Width + Recursion (Take / Skip)
O(2n)Space O(n)After sorting by width, any nesting chain appears left-to-right. Recurse
like LIS: at index i skip it, or take it if it is strictly larger
in both dimensions than the last taken envelope prev.
public int maxEnvelopes(int[][] envelopes) { Arrays.sort(envelopes, (a, b) -> a[0] - b[0]); return best(envelopes, 0, -1); } private int best(int[][] e, int i, int prev) { if (i == e.length) return 0; int skip = best(e, i + 1, prev); int take = 0; if (prev == -1 || (e[i][0] > e[prev][0] && e[i][1] > e[prev][1])) take = 1 + best(e, i + 1, i); return Math.max(skip, take); }
Correct and obvious, but explores every subset — exponential.
BetterSort + O(n2) LIS DP
O(n2)Space O(n)dp[i] = most envelopes in a chain whose outermost is
envelope i. With widths sorted, every envelope that fits inside
i lies to its left; check both dimensions and extend the best one.
public int maxEnvelopes(int[][] envelopes) { Arrays.sort(envelopes, (a, b) -> a[0] - b[0]); int n = envelopes.length, best = 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) dp[i] = Math.max(dp[i], dp[j] + 1); best = Math.max(best, dp[i]); } return best; }
Polynomial, but ~1010 steps at n = 105 — TLE.
OptimalSort (w↑, h↓) + Patience LIS on Heights
O(n log n)Space O(n)Descending heights inside a width group mean two envelopes of the same
width can never both be in a strictly increasing height run. So we can
ignore widths and run the binary-search LIS on heights:
tails[k] = smallest last height of a chain of length k+1.
public int maxEnvelopes(int[][] envelopes) { Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]); int[] tails = new int[envelopes.length]; int size = 0; for (int[] e : envelopes) { int lo = 0, hi = size, h = e[1]; // first tail >= h while (lo < hi) { int mid = (lo + hi) >>> 1; if (tails[mid] < h) lo = mid + 1; else hi = mid; } tails[lo] = h; if (lo == size) size++; } return size; }
Dry runsorted [2,3],[5,4],[6,7],[6,4] → tails
- h=33s··append
- h=434s·append
- h=7347sappend
- h=4347sreplace 4 → size 3 ✔
Sorting plus n binary searches — passes n = 105 easily.
[6,4],[6,7] ascending, heights 4→7
would wrongly nest two width-6 envelopes.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Sort by Width + Recursion (Take / Skip) | O(2n) | O(n) |
| Better | Sort + O(n2) LIS DP | O(n2) | O(n) |
| Optimal | Sort (w↑, h↓) + Patience LIS on Heights | O(n log n) | O(n) |
- Sorting equal widths by height ascending — nests same-width envelopes.
- Using
≤in either dimension — nesting must be strict. - Running the O(n2) DP at n = 105 — times out.
- Say: “this is 2D LIS — sort one dimension away”.
- Explain the tie-break before coding; it is the whole trick.
- Reuse LIS (300) binary search verbatim on the heights.