Russian Doll Envelopes — Hard Problem & Solution

envelopes[i] = [wi, hi]. One envelope fits inside another when both its width and its height are strictly smaller.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Sorting, Binary Search
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

envelopes[i] = [w_i, h_i]. One envelope fits inside another when both its width and its height are strictly smaller.

Return the maximum number of envelopes you can nest, like Russian dolls.

Example 1

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

Example 2

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
Explanation: Equal dimensions do not nest.

Example 3

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

Constraints

1 <= envelopes.length <= 100000
1 <= w_i, h_i <= 100000

How to solve Russian Doll Envelopes

Sorting reduces the two-dimensional nesting to a one-dimensional longest increasing subsequence on the heights. The descending tie-break on height is the whole trick: it makes two envelopes of equal width unable to both appear in an increasing run.

Approach

Sort by width ascending; within equal widths, sort height descending.
Run the patience-sorting LIS on the heights: keep tails, where tails[i] is the smallest possible tail of an increasing subsequence of length i + 1.
For each height, binary search its lower bound in tails and either extend or overwrite.
The answer is tails.length.

Why it works

After the sort, a valid nesting chain is exactly a strictly increasing subsequence of the heights: widths are non-decreasing by construction, and the descending tie-break means any two entries with the same width have non-increasing heights, so they can never both be picked. tails stays sorted, which is what makes the binary search valid, and its length is the LIS length by the standard patience-sorting argument.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Sorting heights ascending within equal widths lets two same-width envelopes nest, over-counting.
The lower bound must use < (strictly increasing), not <=, or equal heights get chained.
The O(n²) dynamic program is the obvious first approach and times out at n = 10^5.

Reference solution

Python

from bisect import bisect_left
from typing import List

def maxEnvelopes(envelopes: List[List[int]]) -> int:
    e = sorted(envelopes, key=lambda x: (x[0], -x[1]))
    tails = []
    for _, h in e:
        i = bisect_left(tails, h)
        if i == len(tails):
            tails.append(h)
        else:
            tails[i] = h
    return len(tails)

JavaScript

var maxEnvelopes = function(envelopes) {
    var e = envelopes.slice().sort(function(a, b) {
        return a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1];
    });
    var tails = [];
    for (var i = 0; i < e.length; i++) {
        var h = e[i][1];
        var lo = 0, hi = tails.length;
        while (lo < hi) {
            var 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;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue