Russian Doll Envelopes

Russian Doll Envelopes

What is this problem about?

The Russian Doll Envelopes interview question gives you a list of envelopes as [width, height] pairs. You can put one envelope inside another if and only if both its width AND height are strictly smaller. Find the maximum number of envelopes you can nest inside each other (like Russian dolls). This is a 2D extension of the Longest Increasing Subsequence (LIS) problem.

Why is this asked in interviews?

This HARD problem is asked at Argo AI, Uber, Goldman Sachs, Microsoft, Meta, Atlassian, Amazon, TikTok, Google, and Bloomberg because it requires a non-obvious sorting trick to reduce a 2D problem to 1D LIS, then applying binary search to compute LIS in O(n log n). It tests whether candidates can identify dimensionality reduction as a problem-solving strategy and apply the patience sorting algorithm.

Algorithmic pattern used

The pattern is sort + binary search LIS. Sort envelopes by width ascending; for equal widths, sort by height descending (crucial to prevent two envelopes with equal width from being nested). Then apply LIS only on the height dimension using binary search (patience sorting): maintain a tails array where tails[i] is the smallest tail of all increasing subsequences of length i+1. Use bisect_left to find the insertion point for each height. The length of tails at the end is the answer.

Example explanation

Envelopes: [[5,4],[6,4],[6,7],[2,3]]

Sort by width ASC, then height DESC for equal widths: [[2,3],[5,4],[6,7],[6,4]]

Heights in order: [3, 4, 7, 4].

Apply LIS on heights:

• 3: tails=[3].
• 4: tails=[3,4].
• 7: tails=[3,4,7].
• 4: bisect_left finds pos 1 (replace 4 with 4 → no change). tails=[3,4,7].

LIS length: 3.

(Envelopes: [2,3] ⊂ [5,4] ⊂ [6,7].)

Common mistakes candidates make

• Sorting heights in ascending order for equal widths — this allows two same-width envelopes to be falsely counted as nestable.
• Using O(n^2) LIS instead of the O(n log n) binary search version — too slow for n up to 10^5.
• Forgetting that both width AND height must be strictly smaller (not ≤).
• Applying the 2D comparison directly with nested loops instead of the sort-then-1D-LIS reduction.

Interview preparation tip

For the Russian Doll Envelopes coding problem, the array, sorting, and binary search interview pattern requires the key sorting insight: equal-width envelopes get descending heights to prevent false nesting. Then binary search LIS is the O(n log n) solution. Interviewers at Goldman Sachs and Atlassian test whether you know the sort trick — explain it before coding. Practice with Python's bisect_left on a few LIS examples to build muscle memory.