Russian Doll Envelopes

Hard
836.

Russian Doll Envelopes

Russian Doll Envelopes is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google, Microsoft and Atlassian interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Russian Doll Envelopes — Solution in Python, Java & C++

Russian Doll Envelopes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Russian Doll Envelopes is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google, Microsoft and Atlassian interviews.

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

Hints for Russian Doll Envelopes

  1. Hint 1

    Sort by width so only the height still needs deciding.

  2. Hint 2

    For equal widths, sort the heights descending — that stops two same-width envelopes being chained.

  3. Hint 3

    The answer is then the longest strictly increasing subsequence of the heights, which binary search finds in n log n.

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

  1. Sort by width ascending; within equal widths, sort height descending.
  2. 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.
  3. For each height, binary search its lower bound in tails and either extend or overwrite.
  4. 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)

Java

public static int maxEnvelopes(int[][] envelopes) {
    int[][] e = envelopes.clone();
    Arrays.sort(e, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(b[1], a[1]));
    int[] tails = new int[e.length];
    int size = 0;
    for (int[] env : e) {
        int h = env[1];
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < h) lo = mid + 1; else hi = mid;
        }
        tails[lo] = h;
        if (lo == size) size++;
    }
    return size;
}

C++

int maxEnvelopes(vector<vector<int>>& envelopes) {
    vector<vector<int>> e = envelopes;
    sort(e.begin(), e.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
    });
    vector<int> tails;
    for (auto& env : e) {
        int h = env[1];
        int lo = 0, hi = (int) tails.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < h) lo = mid + 1; else hi = mid;
        }
        if (lo == (int) tails.size()) tails.push_back(h); else tails[lo] = h;
    }
    return (int) tails.size();
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming