AlgoMaster Logo

Russian Doll Envelopes

Last Updated: April 2, 2026

hard
3 min read

Understanding the Problem

We have a collection of envelopes, each defined by a width and a height. Envelope A fits inside envelope B only when A's width is strictly less than B's width AND A's height is strictly less than B's height. We want to find the longest chain of envelopes where each one nests inside the next.

This is essentially a longest chain problem in two dimensions. If the envelopes only had one dimension, it would reduce to the classic Longest Increasing Subsequence (LIS). The twist is that we need both dimensions to be strictly increasing, and equal dimensions do not count.

The key observation that unlocks the optimal approach: if we can cleverly sort the envelopes to reduce the 2D problem to a 1D problem, we can apply LIS techniques directly on the heights.

Key Constraints:

  • 1 <= envelopes.length <= 10^5 → With up to 100,000 envelopes, O(n^2) dynamic programming (10^10 operations) will time out. We need O(n log n) or better.
  • 1 <= wi, hi <= 10^5 → Widths and heights are positive integers, so we don't need to handle negatives or zeros.
  • Envelopes can have equal widths or equal heights, and equal dimensions do NOT satisfy the "strictly less than" condition. This is a subtle but critical constraint.

Approach 1: Dynamic Programming (O(n^2))

Intuition

The most natural way to think about this problem is as a variant of Longest Increasing Subsequence in two dimensions. If we sort the envelopes by width (and break ties by height), then for each envelope we can look at all previous envelopes and check if the current one can contain them.

This is the same idea as the classic O(n^2) LIS: for each element, check all elements before it and extend the longest valid chain. The only difference is that our "increasing" condition requires both width and height to be strictly increasing.

Algorithm

  1. Sort envelopes by width ascending. For equal widths, sort by height ascending.
  2. Create a dp array where dp[i] represents the length of the longest chain ending with envelope i.
  3. Initialize every dp[i] = 1 (each envelope is a chain of length 1 by itself).
  4. For each envelope i, look at all previous envelopes j (where j < i). If envelopes[j] fits inside envelopes[i] (both width and height are strictly less), then dp[i] = max(dp[i], dp[j] + 1).
  5. Return the maximum value in the dp array.

Example Walkthrough

1Sorted by width ASC, height ASC: [[2,3], [5,4], [6,4], [6,7]]
0
[2,3]
1
[5,4]
2
[6,4]
3
[6,7]
1/5
1Initialize dp: every envelope is a chain of 1
0
1
1
1
2
1
3
1
1/5

Code

This approach works but is too slow for n = 10^5. What if we sorted the envelopes so that the width condition is automatically satisfied, reducing it to a 1D LIS problem on heights that we can solve in O(n log n)?

Approach 2: Sort + LIS with Binary Search (Optimal)

Intuition

If we sort envelopes by width ascending, then any subsequence in sorted order has non-decreasing widths. But we need strictly increasing widths and heights. The trick: for equal widths, sort heights descending. This prevents two same-width envelopes from both appearing in the LIS on heights. After sorting, the problem becomes exactly LIS on the heights array, which we solve in O(n log n) using patience sorting (binary search with a tails array).

Algorithm

  1. Sort envelopes by width ascending. For equal widths, sort by height descending.
  2. Extract just the heights into an array.
  3. Run the O(n log n) LIS algorithm on the heights: maintain a tails array where tails[i] is the smallest tail of any increasing subsequence of length i+1. For each height, binary search for the leftmost position where tails[pos] >= height. Replace or append accordingly.
  4. The length of tails is the answer.

Example Walkthrough

1Sorted envelopes: [2,3], [5,4], [6,7], [6,4]. Heights: [3, 4, 7, 4]
0
3
1
4
2
7
3
4
1/6
1tails array: tracks smallest ending height per LIS length
1/6

Code