Command Palette

Search for a command to run...

Hectal
Problem 31.2 · DP on Strings and SequencesHard

Russian Doll Envelopes

PatternLongest Increasing SubsequenceBinary Search on an Index

What it teaches: Turn a 2D chain into 1D LIS by sorting width ascending and height descending.

Practise it on judges as “Russian Doll Envelopes”.

The problem

An envelope fits inside another if both its width and height are strictly smaller. Return the most envelopes you can nest.

Example 1

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3

[2,3] → [5,4] → [6,7].

Constraints

  • 1 ≤ n ≤ 10⁵

Pattern clues in the wording

  • → Chain of strictly increasing pairs

These clues point to Longest Increasing Subsequence: dp[i] is the longest increasing run ending at i; a patience-sorting version with binary search gets O(n log n).

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
envelopes = [[5,4],[6,4],[6,7],[2,3]]
3
2
envelopes = [[1,1],[1,1],[1,1]]
1

From slow to fast

Approaches

1. Sort + LIS · O(n log n)
1

Sort + LIS

Time O(n log n) Space O(n)

Sort (w ascending, h descending); run the tails LIS on heights.

Approach 1
import java.util.Arrays;

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 size = 0;
        for (int[] e : envelopes) {
            int lo = 0, hi = size, h = e[1];
            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;
    }
}

Verdict: The descending tie-break is the trick.

Before you submit

Edge cases and common mistakes

Test these inputs

  • All identical (1)
  • Same width, different heights

Mistakes people make

  • Sorting heights ascending for equal widths (lets equal widths nest).

Interview

Follow-up questions

What about boxes in 3D?