Russian Doll Envelopes — Sort Plus LIS Binary Search Guide

Problem Statement#

Given a 2D array envelopes[i] = [w, h], return the maximum number of envelopes that can be nested where one fits strictly inside another (both width and height strictly smaller).

Constraints:

• 1 <= envelopes.length <= 10^5
• 1 <= w, h <= 10^5

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

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

Why This Problem Matters#

LeetCode 354 is a hard binary search interview classic at Google, Amazon, and Meta. It looks 2D but the right reduction collapses it to one dimension. The reduction itself is the test — interviewers want to see whether you can recognize that sorting one dimension lets you solve the other independently.

It also exercises patience sorting: the elegant O(n log n) algorithm for Longest Increasing Subsequence. Many candidates only know the O(n^2) DP, which times out at n = 10^5. Demonstrating the binary search variant signals comfort with FAANG O(log n) thinking and the search-on-answer family more broadly.

The "sort by one key, run a 1D algorithm on the other" pattern reappears in scheduling, interval problems, and offline query processing. Russian Doll Envelopes is the textbook teaching example.

The Core Insight#

Sort envelopes by width ascending. For ties on width, sort by height descending. The descending tie-break prevents two envelopes with equal width from forming an increasing height sequence — which would be wrong because equal width cannot nest. Then run patience-sorted LIS on the heights.

Visual Dry Run#

Input [[5,4],[6,4],[6,7],[2,3]]. Sort by width asc, height desc: [[2,3],[5,4],[6,7],[6,4]]. Heights to LIS: [3, 4, 7, 4].

LIS length is 3.

Solution (Optimal)#

from bisect import bisect_left
 
class Solution:
    def maxEnvelopes(self, envelopes):
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        tails = []
        for _, h in envelopes:
            idx = bisect_left(tails, h)
            if idx == len(tails):
                tails.append(h)
            else:
                tails[idx] = h
        return len(tails)

var maxEnvelopes = function(envelopes) {
    envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    const tails = [];
    for (const [, h] of envelopes) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < h) lo = mid + 1; else hi = mid;
        }
        if (lo === tails.length) tails.push(h);
        else tails[lo] = h;
    }
    return tails.length;
};

Time: O(n log n) — sorting plus binary search per height. Space: O(n) — tails array.

Common Mistakes#

• Sorting both width and height ascending, which lets equal widths form a fake increasing sequence.
• Using bisect_right for strict LIS, which incorrectly allows equal heights.
• Running O(n^2) LIS DP and timing out for n = 10^5.
• Forgetting that nesting requires strict inequality in both dimensions.
• Sorting only by width without breaking ties properly.

Interview Tips#

• Talk about the reduction first, then implement.
• Justify the descending tie-break aloud — that single sentence often closes the loop.
• Mention bisect_left versus bisect_right distinction explicitly.

Follow-up Questions#

• What if envelopes only need non-strict nesting? Tie-break ascending and use bisect_right.
• 3D version (LC unbounded boxes)? Sort one dim, then 2D LIS — usually too slow without DP tricks.
• How would you reconstruct the actual nesting sequence? Store predecessor indices alongside tails.
• What if n = 10^7? Talk about external sort and incremental LIS.
• Same problem with rotation allowed? Normalize each envelope to (min, max) then run.

Key Takeaways#

• LC 354 reduces 2D nesting to 1D LIS via a clever sort.
• Sort by width ascending, height descending to preserve strict-nesting semantics.
• Patience-sorted LIS gives O(n log n) using bisect_left for strict LIS.
• The tails array does not store the actual subsequence — just length.
• Equal widths must not be allowed to chain; the tie-break enforces this.
• The same pattern handles offline 2D dominance queries.
• Always reach for patience sorting whenever LIS appears with n greater than 10^4.