Russian Doll Envelopes
Asked at Atlassian
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | HARD | View all Atlassian questions → |
How to Think About It
Brute force: try all pairs and check if one fits inside another, O(n^3) DP.
Sort envelopes by width ascending, then reduce to longest increasing subsequence on heights.
Problem: simple LIS on heights allows equal heights, but we need strict inequality on both dimensions.
Sort by width ascending and by height descending for same widths, then LIS on heights avoids width ties.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.