How do you approach Russian Doll Envelopes?

If you sort by width, you reduce to LIS on heights - but only if you handle ties correctly.

What is the time complexity of Russian Doll Envelopes?

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

What are common mistakes on Russian Doll Envelopes?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Russian Doll Envelopes

HardAlgorithms

Description

You are given a 2D array of integers `envelopes` where `envelopes[i] = [w_i, h_i]` represents the width and the height of an envelope. One envelope can fit into another if and only if both the width and height of one envelope are **strictly greater** than the width and height of the other. Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other). **Note:** You cannot rotate an envelope.

Example 1

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

Output: 3

Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] → [5,4] → [6,7]).

Example 2

Input: envelopes = [[1,1],[1,1],[1,1]]

Output: 1

Constraints

- 1 <= envelopes.length <= 10^5 - envelopes[i].length == 2 - 1 <= w_i, h_i <= 10^5

Russian Doll Envelopes: approach, complexity and pitfalls

A hard binary search problem, graded against 5 test cases (2 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

If you sort by width, you reduce to LIS on heights - but only if you handle ties correctly.
When widths are equal, sort by height descending. That guarantees you never pick two envelopes with the same width in the LIS.
Run patience-sort LIS on the heights array in O(n log n).

The optimal approach

Show the approach: Sort + LIS in O(n log n)

Sort envelopes by width ascending. For equal widths, break the tie by sorting heights *descending* - this way an LIS over the height array can never pick two envelopes that share a width (the second would need a strictly larger height, but the descending tie-break placed the larger height first).

Then run the standard patience-sort LIS on the heights:

- Maintain a tails array where `tails[i]` is the smallest height ending an increasing subsequence of length i+1.

- For each height, binary-search the leftmost slot whose value `>= h` and overwrite it.

- The answer is `tails.length`.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.