AlgoMaster Logo

Russian Doll Envelopes

hardFrequency5 min readUpdated June 23, 2026

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 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 complication is that we need both dimensions to be strictly increasing, and equal dimensions do not count.

If we can sort the envelopes so that the width condition is handled by the ordering itself, the problem reduces to a 1D LIS 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.
  • Envelopes can have equal widths or equal heights, and equal dimensions do NOT satisfy the "strictly less than" condition. The sorting step has to account for this, otherwise two same-width envelopes can both end up in the chain.

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

Intuition

Treat this as a variant of Longest Increasing Subsequence in two dimensions. Sort the envelopes by width (breaking ties by height), then for each envelope, look at all previous envelopes and check whether 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 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

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

Code

This is too slow for n = 10^5. The next approach replaces the inner loop with a binary search by first sorting the envelopes so the width condition is satisfied by the ordering, reducing the problem to a 1D LIS on heights in O(n log n).

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

Intuition

Sort envelopes by width ascending, so any left-to-right subsequence has non-decreasing widths. We still need strictly increasing widths and heights. 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 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 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

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

Code