Russian Doll Envelopes

Hard Dynamic Programming 1D DP Original on LeetCode

Russian Doll Envelopes is a hard dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (sort + binary-search lis), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from sort + o(n²) dp up.

Problem

You are given a list of envelopes, where envelopes[i] = [w_i, h_i] is the width and height of one envelope.

An envelope can be put inside another only if it is strictly smaller in both width and height. Envelopes cannot be rotated.

Return the largest number of envelopes you can nest one inside another, like a set of Russian dolls.

Examples

Example 1

Input
envelopes = [[4, 5], [4, 7], [6, 8], [2, 3], [7, 9]]
Output
4
Why
[2, 3] fits into [4, 5], which fits into [6, 8], which fits into [7, 9]. [4, 7] cannot hold [4, 5] because their widths are equal.

Example 2

Input
envelopes = [[3, 3], [3, 3], [3, 3]]
Output
1
Why
Identical envelopes never fit into each other.

Example 3

Input
envelopes = [[1, 9], [2, 8], [3, 7]]
Output
1
Why
Each wider envelope is shorter than the previous one, so no two can be nested.

Constraints

  • 1 <= envelopes.length <= 10^5
  • envelopes[i].length == 2
  • 1 <= w_i, h_i <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Sort + O(n²) DPO(n²)O(n)
Optimal (sort + binary-search LIS)O(n log n)O(n)

1Sort + O(n²) DP

TimeO(n²)Every pair (j, i) is compared once; the sort is O(n log n).
SpaceO(n)The dp array.

Sort by width (then height). dp[i] is the longest chain that ends with envelope i as the outermost one: one more than the best dp[j] over earlier envelopes that are strictly smaller in both dimensions.

  1. Sort envelopes by width, then by height.
  2. dp[i] = 1 + max(dp[j]) over j < i with w[j] < w[i] and h[j] < h[i] (or 1 if none).
  3. Return the largest dp[i].
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        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][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;
    }
}

2Optimal (sort + binary-search LIS)

TimeO(n log n)The sort plus one binary search per envelope.
SpaceO(n)The `tails` array holds at most n heights.

Sort by width ascending and, inside one width, by height descending. Now any strictly increasing run of heights automatically uses distinct widths (heights of one width go down, so at most one of them can be in an increasing run). The answer is the longest strictly increasing subsequence of heights, found with the patience method: tails[k] is the smallest possible last height of an increasing run of length k + 1.

  1. Sort by (width asc, height desc).
  2. For each height h: find the first index in tails with value >= h (lower bound).
  3. Replace that entry with h, or append h if no such index exists.
  4. Return the length of tails.
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1]));
        int[] tails = new int[envelopes.length];
        int len = 0;
        for (int[] e : envelopes) {
            int lo = 0, hi = len;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < e[1]) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = e[1];
            if (lo == len) len++;
        }
        return len;
    }
}

Edge cases to test

  • A single envelope
  • Many envelopes with the same width (only one of them can be used)
  • Duplicate envelopes
  • Envelopes that are already nested in input order, or in reverse order

Hints

Hint 1

After sorting by width, the problem looks like a longest strictly increasing subsequence on heights.

Hint 2

Equal widths are the trap: two envelopes with the same width must never both be picked. How can the sort order of heights inside one width prevent that?

Hint 3

Sort by width ascending and, for equal widths, by height descending. Then run the O(n log n) longest increasing subsequence on heights.

FAQ

What is the best time complexity for Russian Doll Envelopes?

Optimal (sort + binary-search LIS) runs in O(n log n) time and O(n) extra space. The sort plus one binary search per envelope.

Which pattern does Russian Doll Envelopes use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Russian Doll Envelopes?

Yes. Sort + O(n²) DP takes O(n²) time and O(n) space. Sort by width (then height).

Which edge cases should I test for Russian Doll Envelopes?

A single envelope; Many envelopes with the same width (only one of them can be used); Duplicate envelopes; Envelopes that are already nested in input order, or in reverse order.