Russian Doll Envelopes (LC 354)

Problem Statement

Given envelopes[i] = [w_i, h_i], one envelope fits inside another iff both its width and height are strictly smaller. Return the maximum number of envelopes you can nest.

Example 1:

Input:  [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: [2,3] -> [5,4] -> [6,7].

Example 2:

Input:  [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

• 1 <= envelopes.length <= 10^5
• 1 <= w_i, h_i <= 10^5

Difficulty: Hard

---

Pattern Recognition

• Input structure: 2D points (width, height).
• What are we optimizing? longest chain under strict-2D dominance.
• Pattern: reduce to 1D Longest Increasing Subsequence (LIS) by a clever sort.
• Why: if you sort by width ascending and break ties by height descending, then an LIS on the height sequence corresponds exactly to a valid nested chain — the descending tie-break prevents two envelopes with the same width from ending up together in the LIS.

This reduction is a Google-interviewer favorite because it's a great example of "transform to a known subproblem."

---

Approach

Brute Force — DP on Pairs

Sort by width. dp[i] = longest chain ending at i. For each i, scan all j < i with w[j] < w[i] and h[j] < h[i]. O(n^2).

Optimal — Sort + LIS Binary Search

Key Insight: After sorting by (w asc, h desc), run classic O(n log n) patience-sort LIS on the h sequence. The descending tie on h ensures that two envelopes with equal w cannot both be selected, because their hs appear in decreasing order and LIS is strictly increasing.

Why the tie-break matters:

• If two envelopes share a width w, neither can nest into the other.
• With h ascending on equal w, LIS might pick both hs — wrong.
• With h descending, LIS sees ..., h_big, h_small, ..., cannot pick both.

Steps:

1. sort(envelopes) by width ascending; ties by height descending.
2. Extract heights.
3. Run strict-increasing LIS (lower_bound) on heights.

Time: O(n log n). Space: O(n).

---

Walkthrough

[[5,4],[6,4],[6,7],[2,3]].

Sort by (w asc, h desc): [[2,3],[5,4],[6,7],[6,4]].

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

LIS via patience sort:

x	lower_bound	tails
3	end → append	[3]
4	end → append	[3, 4]
7	end → append	[3, 4, 7]
4	index 1 → replace	[3, 4, 7]

tails.length = 3. Answer: 3.

Sanity: with tie [6,7] before [6,4], the 4 replaces the middle but cannot extend — which prevents the illegal pairing [6,4] with [6,7].

---

Implementation

TypeScript

function maxEnvelopes(envelopes: number[][]): number {
    // Sort by width ascending; on tie, height descending
    envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);

    // Strict-increasing LIS on heights — patience sort
    const tails: number[] = [];
    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;
}

C++

int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });
    vector<int> tails;
    for (auto& e : envelopes) {
        int h = e[1];
        auto it = lower_bound(tails.begin(), tails.end(), h);
        if (it == tails.end()) tails.push_back(h);
        else *it = h;
    }
    return tails.size();
}

Watch out:

1. Sorting heights ascending on tied widths is the classic bug — you'll over-count.
2. Using upper_bound (non-strict) on heights lets equal heights stack, also incorrect.
3. At n = 10^5, an O(n^2) solution is too slow; the O(n log n) is mandatory.

---

Complexity Analysis

	Time	Space
DP O(n^2)	O(n^2)	O(n)
Sort + Patience LIS	O(n log n)	O(n)

Bottleneck: sorting dominates. The LIS scan is itself O(n log n).

---

Edge Cases

1. Single envelope — answer 1.
2. All identical envelopes — answer 1; tie-break + strict LIS blocks extension.
3. All widths unique — regular LIS on heights.
4. All widths equal, heights varied — only one can nest; descending-h tie-break + strict LIS enforces this.
5. Already nested input — LIS length = n.
6. Reverse-nested input — LIS length = 1 after sort.

---

Related Problems

• LC 300 — Longest Increasing Subsequence — The 1D base problem.
• LC 1691 — Maximum Height by Stacking Cuboids — 3D nesting with sort-by-max-dim + DP.
• LC 646 — Maximum Length of Pair Chain — Greedy by end; simpler 1D version.
• LC 1235 — Maximum Profit in Job Scheduling — Sort + DP + binary search; similar flavor.

---

What Is Expected at Each Level

Junior: Attempts O(n^2) DP, explains the dominance relation. May not see the LIS reduction.

Mid-level: Makes the LIS connection with a nudge, implements the sort + patience-sort correctly, justifies the tie-break.

Senior (L4 target): States the reduction immediately, explains the tie-break with a two-envelope counter-example, and writes the O(n log n) solution in one pass. Discusses the 3D generalization (LC 1691) and whether the trick still works (no — requires DP).