Russian Doll Envelopes — 2D LIS with the Tie-Breaker Trick

Problem Statement#

You are given a list of envelopes where each entry is a pair [w, h] representing the width and height of an envelope. One envelope fits inside another only when both the width and the height of the outer envelope are strictly larger than those of the inner envelope. Rotation is not allowed.

Return the maximum number of envelopes that can be Russian-doll nested into each other.

Example: envelopes = [[5,4],[6,4],[6,7],[2,3]] returns 3. The chain [2,3] -> [5,4] -> [6,7] nests three envelopes; we cannot include both [6,4] and [6,7] because their widths are equal.

Constraints: up to 10^5 envelopes with coordinates up to 10^5. That immediately rules out an O(n^2) baseline LIS — we need an O(n log n) DP.

Why This Problem Matters#

Russian Doll Envelopes is a textbook FAANG interview question because it sits at the intersection of three DP staples — sorting, Longest Increasing Subsequence, and clever tie-breaking. Companies like Google, Amazon, Microsoft, Meta, and Goldman Sachs use it to test whether a candidate can recognize a 1D pattern hidden inside a 2D problem and, more importantly, whether they can reason about why a greedy sort works.

The problem is also a beautiful demonstration of "DP plus invariants." We do not just memoize a recurrence — we engineer the input so that a simpler DP (LIS) becomes correct. That kind of preprocessing is exactly the optimal substructure thinking interviewers look for.

The Core Insight (Recurrence)#

Imagine we sorted envelopes by width ascending. After sorting, can we just run LIS on the heights? Almost — but if two envelopes share the same width, both might end up in the increasing subsequence even though they cannot nest (equal widths violate the strict inequality).

The trick: when widths are equal, sort by height descending. After this dual-key sort, any LIS on the height array becomes a valid chain because:

• Different widths are already in increasing order, so width strictly increases along any subsequence.
• Equal widths sit in decreasing height order, so a strictly increasing height subsequence can pick at most one of them.

That reduces the 2D nesting problem to a classic 1D LIS recurrence:

LIS[i] = 1 + max(LIS[j]) for all j with j less than i and h[j] less than h[i].

The standard O(n^2) tabulation is too slow. We use the patience-sorting variant: maintain a tails array where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1. Binary search the insertion point with bisect_left (strict less-than) and the array length is the LIS length.

Building the DP Solution (Recursion to Memo to Tabulation)#

Naive recursion: for each envelope, try every smaller envelope as the previous element. That is exponential. Memoizing on index gives O(n^2) time and O(n) space — the textbook DP. Tabulation: fill dp[i] left-to-right. Both are correct but too slow for n up to 10^5.

The patience-sort optimization replaces the inner "find the best previous LIS" loop with a binary search. We are still computing the same DP values implicitly — we are just storing them in a way that lets us update in O(log n) per element.

Visual Dry Run (DP Table Trace)#

Take envelopes = [[5,4],[6,4],[6,7],[2,3],[5,4]].

After sort-by-width-asc, height-desc: [[2,3],[5,4],[5,4],[6,7],[6,4]]. Heights extracted: [3, 4, 4, 7, 4].

Patience LIS trace on heights:

• Start tails = [].
• See 3: tails = [3].
• See 4: 4 is greater than 3, append. tails = [3, 4].
• See 4 again: bisect_left returns index 1 (replacing 4 with 4, no growth). tails = [3, 4]. The descending-height tie-break is what guarantees this no-op behavior for equal widths.
• See 7: append. tails = [3, 4, 7].
• See 4: bisect_left returns 1. tails = [3, 4, 7]. The 7 stays as a witness that an LIS of length 3 exists.

Final length 3. The three nested envelopes correspond to widths 2, 5, 6 with heights 3, 4, 7.

Optimized Solution — Space-Optimized Python and JavaScript#

Python#

from bisect import bisect_left
from typing import List
 
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Sort: width asc, height desc on ties.
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        tails: List[int] = []
        for _, h in envelopes:
            pos = bisect_left(tails, h)
            if pos == len(tails):
                tails.append(h)
            else:
                tails[pos] = h
        return len(tails)

JavaScript#

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;
    let 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;
};

Complexity Analysis#

• Time: O(n log n). Sorting dominates and the LIS pass is also O(n log n) thanks to binary search.
• Space: O(n) for the tails array. The sort is in place in most languages.
• Reading the chain itself requires reconstructing parent pointers, which costs an extra O(n) memory but does not change asymptotic complexity.

Common Mistakes#

• Sorting by height ascending on ties. This lets two equal-width envelopes form an increasing height subsequence, producing a wrong answer such as 4 instead of 3.
• Using bisect_right instead of bisect_left. That allows duplicates and breaks the strict inequality on heights.
• Trying the O(n^2) DP at scale. It is correct but Time-Limit-Exceeded on the large LeetCode constraint of 10^5.
• Mutating the input without checking whether the interviewer cares — clarify before sorting in place.
• Assuming rotation is allowed. The classic problem disallows it; some variants permit min(w,h) and max(w,h) swaps.

Interview Tips#

• Begin by recognizing this is "LIS with a twist." Verbalize: "If I can fix one dimension monotonically, the other reduces to LIS."
• Walk through why the descending-height tie-break is needed. Interviewers love this micro-proof; it separates strong candidates from rote memorizers.
• Start with the O(n^2) DP, then optimize to O(n log n) only after discussing constraints. Never jump to patience sort without justification.
• Mention real-world analogues: stacking boxes, scheduling jobs with two-dimensional constraints, courier package nesting.

Follow-up Questions#

• Print the actual nesting chain, not just its length. Hint: store predecessor indices alongside tails.
• Allow rotation so an envelope [a, b] can be used as either [a, b] or [b, a]. How does the recurrence change?
• Generalize to k dimensions. Why does the trick stop scaling above two dimensions?
• What if envelopes can be reused multiple times? That breaks LIS; you would need a DAG longest-path DP.

Key Takeaways#

• Russian Doll Envelopes is a 2D nesting problem that collapses to a 1D LIS DP with the right preprocessing.
• The "width ascending, height descending" sort is the load-bearing trick. Without it, the LIS overcounts equal widths.
• Patience-sort LIS gives O(n log n), which is required for the LeetCode constraints — the O(n^2) tabulation is a teaching baseline only.
• The solution exemplifies the FAANG interview pattern of recognizing optimal substructure across dimensions and applying memoization or tabulation idioms.
• Always state your DP state, transition, and base case out loud before coding — that is what the rubric scores.
• Generalizations (rotation, higher dimensions, path reconstruction) are great follow-ups to prepare for senior-level loops.