Russian Doll Envelopes

1. Define the problem

You are given a 2D array envelopes where envelopes_i = [w_i, h_i] represents the width and height of an envelope. One envelope can fit into another if and only if both its width and height are strictly smaller than the other envelope's width and height. Return the maximum number of envelopes you can Russian doll (put one inside another, inside another, and so on). This looks like a 2D problem, but it reduces to a 1D one you may already know: the longest increasing subsequence . First sort envelopes by width ascending — but for envelopes that share the same width, sort by height descending. That second rule matters: since two same-width envelopes can never nest inside each other anyway, sorting their heights downward stops the next step from mistakenly stringing them together. Once sorted, the answer is just the longest increasing run of heights, found efficiently with patience sorting , a technique that tracks the smallest possible "tail" height for every subsequence length seen so far.

Constraints

1 ≤ envelopes.length ≤ 10⁵
envelopes_i.length == 2
1 ≤ w_i, h_i ≤ 10⁵

Example

Inputenvelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]

Output3

Explanation The maximum number of envelopes you can Russian doll is 3: [2,3] => [5,4] => [6,7]. Note that [6,4] cannot fit inside [5,4] or vice versa since neither dimension is strictly larger.

2. Know the words first

In plain terms

Patience sorting: A way to find the longest increasing subsequence in O(n log n): keep a list of the smallest tail value achievable for each subsequence length, and use binary search to find where each new value belongs.

3. Visualize the solution

The row is the tails list: the smallest height that can end a chain of each length

chain of 1—

chain of 2—

chain of 3—

Statussorted

Sorted by width asc, height desc on ties: [[2,3],[5,4],[6,7],[6,4]] — the heights to scan, in order, are 3, 4, 7, 4. No chains found yet, so every cell is blank.

What happens in this step

sorted envelopes: [2,3], [5,4], [6,7], [6,4]
heights in this order: 3, 4, 7, 4

Note [6,7] comes before [6,4]: same width 6, but sorted by height descending so they can't falsely chain.

tails = []

Step 1 of 6

Steps to visualize

Sort envelopes by width ascending; break ties by sorting height descending, so equal-width envelopes never chain together.
The row below is the tails list. Cell "chain of 1" holds the smallest height that can end a chain of one envelope, "chain of 2" the smallest height that can end a chain of two, and so on.
A cell showing — means no chain of that length has been found yet. Three cells is as long as this example can get, since there are only four envelopes and two of them share a width.
For each height in the sorted order, find the first cell holding a height that is not smaller than it.
If every filled cell is smaller, fill the next empty cell (the chain just got longer). Otherwise, overwrite that cell with the smaller height.
The number of filled cells at the end is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the tails list: the smallest height that can end a chain of each length

chain of 1—

chain of 2—

chain of 3—

Statussorted

Sorted by width asc, height desc on ties: [[2,3],[5,4],[6,7],[6,4]] — the heights to scan, in order, are 3, 4, 7, 4. No chains found yet, so every cell is blank.

What happens in this step

sorted envelopes: [2,3], [5,4], [6,7], [6,4]
heights in this order: 3, 4, 7, 4

Note [6,7] comes before [6,4]: same width 6, but sorted by height descending so they can't falsely chain.

tails = []

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function maxEnvelopes(envelopes) {
  const sorted = [...envelopes].sort((a, b) => (a[0] - b[0]) || (b[1] - a[1]));
  const tails = [];

  for (const [, height] of sorted) {
    let lo = 0;
    let hi = tails.length;

    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < height) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    if (lo === tails.length) {
      tails.push(height);
    } else {
      tails[lo] = height;
    }
  }

  return tails.length;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]`	`3`	example from the docstring
`envelopes = [[1, 1]]`	`1`	smallest valid input: a single envelope
`envelopes = [[4, 5], [4, 6], [4, 7]]`	`1`	equal widths can never nest, regardless of height
`envelopes = [[1, 1], [2, 2], [3, 3], [4, 4]]`	`4`	every envelope strictly nests inside the next
`envelopes = [[1, 3], [2, 3], [3, 3]]`	`1`	equal heights across different widths can never nest either
`envelopes = [[3, 4], [3, 4], [5, 6]]`	`2`	duplicate envelopes that cannot nest inside each other

Russian Doll Envelopes