HardArrayBinary SearchDynamic ProgrammingSortingLongest Increasing SubsequenceUpdated Sep 2026

354. Russian Doll Envelopes

Asked at Atlassian

Difficulty

Hard

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given a list of envelopes. Each envelope is a pair [width, height].

One envelope can be placed inside another only if both its width and its height are strictly smaller. So [2,3] fits inside [5,4], but [5,4] does not fit inside [6,4] because the heights are equal. You may not rotate an envelope.

Return the largest number of envelopes you can stack this way, one inside the next.

Nesting needs strict growth in both sides

envelopes[5,4][6,4][6,7][2,3]0123The green envelopes form the best chain of length 3
[2,3] → [5,4] → [6,7] is the longest chain; [6,4] cannot join because its height ties with [5,4].

Constraints

  • ●1 <= envelopes.length <= 10^5
  • ●envelopes[i].length == 2
  • ●1 <= wi, hi <= 10^5

Examples

Example 1
Inputenvelopes = [[5,4],[6,4],[6,7],[2,3]]
Output3
WhyThe chain [2,3] → [5,4] → [6,7] works: each step is strictly bigger in both width and height. No chain of 4 exists, so the answer is 3.
Example 2
Inputenvelopes = [[1,1],[1,1],[1,1]]
Output1
WhyAll envelopes are identical. Strict inequality fails, so no envelope fits inside another. You can only use one.

Asked At

1 companies
CompanyDifficulty
AtlassianHardView all Atlassian questions →

How to Think About It

1

Brute force: try all pairs and check if one fits inside another, O(n^3) DP.

2

Sort envelopes by width ascending, then reduce to longest increasing subsequence on heights.

3

Problem: simple LIS on heights allows equal heights, but we need strict inequality on both dimensions.

4

Sort by width ascending and by height descending for same widths, then LIS on heights avoids width ties.

5

Optimal: sort envelopes by width ascending then height descending, find LIS on heights using patience sorting with binary search in O(n log n).

Optimal Approach

Sort envelopes by width ascending, and for envelopes with the same width, sort by height descending. This ensures that when we compute the longest increasing subsequence on heights, no two envelopes with the same width can both be selected (since their heights are in descending order). After sorting, the problem reduces to finding the LIS of the height sequence using patience sorting with binary search, which runs in O(n log n) time. The length of this LIS is the maximum number of nested envelopes.

Sort, then LIS on heights

sorted[2,3][5,4][6,7][6,4]0123Same width 6: taller one first, so [6,7] can never befollowed by [6,4]heightsLIS = 334740123Longest strictly increasing subsequence of heights is3, 4, 7sort by (w asc, h desc)tails = patience piles on hanswer = len(tails) = 3
Sorting by width ascending and height descending blocks same-width pairs, so a plain LIS on heights is safe.
ComplexityTime O(n log n)Space O(n)Sorting costs O(n log n), and each height does one binary search over the tails array, which holds at most n values.

What Trips People Up in Real Interviews

1

Clarify that both width AND height must be strictly smaller for one envelope to fit inside another.

2

Explain why sorting by width ascending alone is insufficient due to ties.

3

Mention the trick of sorting heights descending within the same width to prevent selecting two envelopes with the same width.

4

Discuss the patience sorting approach for LIS in O(n log n).

5

Address edge cases like empty input or single envelope.

Solution Code

O(n log n) time
import bisect

class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        heights = [h for _, h in envelopes]
        
        tails = []
        for h in heights:
            pos = bisect.bisect_left(tails, h)
            if pos == len(tails):
                tails.append(h)
            else:
                tails[pos] = h
        
        return len(tails)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Russian Doll Envelopes problem?

Given a 2D array of envelopes where each envelope is [width, height], find the maximum number of envelopes you can Russian doll (one fits inside another). Envelope A fits inside B if and only if A.width < B.width and A.height < B.height.

How do you solve Russian Doll Envelopes?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Russian Doll Envelopes?

Russian Doll Envelopes is asked at Atlassian. It is a hard difficulty problem.

What are common mistakes on Russian Doll Envelopes?
  • Clarify that both width AND height must be strictly smaller for one envelope to fit inside another.
  • Explain why sorting by width ascending alone is insufficient due to ties.
  • Mention the trick of sorting heights descending within the same width to prevent selecting two envelopes with the same width.
  • Discuss the patience sorting approach for LIS in O(n log n).
  • Address edge cases like empty input or single envelope.