Russian Doll Envelopes
Hard · Dynamic Programming · Array · Binary Search · Dynamic Programming · Sorting
Problem
You are given a list envelopes where envelopes[i] = [wi, hi] is the width and height of an envelope. Envelope A fits inside envelope B only if A's width and height are both strictly smaller than B's.
Envelopes cannot be rotated. Return the largest number of envelopes you can nest one inside another.
Examples
Input: envelopes = [[4,5],[4,6],[6,7],[2,3],[1,1]] Output: 4
Nest [1,1] in [2,3] in [4,5] in [6,7]. [4,6] could take the place of [4,5], but not join it: their widths are equal.
Input: envelopes = [[2,2],[2,2]] Output: 1
Identical envelopes cannot contain each other.
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3
[2,3] inside [5,4] inside [6,7]. [6,4] fits nothing: its height equals [5,4]’s.
Constraints
- 1 <= len(envelopes) <= 10^5
- envelopes[i] == [wi, hi]
- 1 <= wi, hi <= 10^5
Approaches
- Sort, then quadratic DP — time O(n²), space O(n)
Follow-up
Boxes have three dimensions: sort by one, and you need the longest chain that increases in the other two, which no longer reduces to a single LIS. The O(n²) DP still works; faster needs divide and conquer (CDQ) or a 2D data structure, O(n log² n).
Related problems
Start free on Cariara · Coding problems · System design studio
