Code Implementation

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes):
        # Sort by width asc, and by height desc for equal widths
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        heights = [h for w, h in envelopes]
        dp = []
        for h in heights:
            idx = bisect_left(dp, h)
            if idx == len(dp):
                dp.append(h)
            else:
                dp[idx] = h
        return len(dp)
      

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    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> dp;
        for (auto& env : envelopes) {
            int h = env[1];
            auto it = lower_bound(dp.begin(), dp.end(), h);
            if (it == dp.end())
                dp.push_back(h);
            else
                *it = h;
        }
        return dp.size();
    }
};
      

import java.util.*;

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        List<Integer> dp = new ArrayList<>();
        for (int[] env : envelopes) {
            int h = env[1];
            int idx = Collections.binarySearch(dp, h);
            if (idx < 0) idx = -(idx + 1);
            if (idx == dp.size()) dp.add(h);
            else dp.set(idx, h);
        }
        return dp.size();
    }
}
      

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

Problem Description

Given a list of envelopes, each described by a pair [width, height], you must determine the maximum number of envelopes you can nest ("Russian doll style"). An envelope A can fit into envelope B if and only if both A's width and height are strictly less than B's width and height. You cannot rotate envelopes, and each envelope can be used at most once. Return the largest number of envelopes that can be nested inside each other.

Thought Process

At first glance, this problem looks similar to finding the longest increasing subsequence (LIS), but in two dimensions. A brute-force approach would involve trying all possible envelope orderings, checking which ones can be nested—a solution that quickly becomes infeasible due to the number of combinations.

To optimize, we notice that if we sort the envelopes appropriately, we can reduce the problem to a 1D LIS problem. The main challenge is dealing with both width and height, as envelopes with the same width but different heights cannot be nested.

The key insight is to sort by width (ascending) and, for equal widths, by height (descending). This prevents envelopes with equal widths from being incorrectly nested. Once sorted, we only need to find the LIS of the heights, as the width constraint is already handled by the sorting.

Solution Approach

We can solve the problem efficiently by following these steps:

1. Sort the envelopes: Sort the array first by width in ascending order. For envelopes with the same width, sort by height in descending order. This ensures we never pick two envelopes with the same width in our sequence, as their heights will be decreasing.
2. Extract heights: Once sorted, create a new list consisting of just the heights of the envelopes.
3. Find the LIS: The problem now reduces to finding the length of the longest increasing subsequence in the heights list. This can be done in O(n log n) time using binary search and a dynamic array:
   • Iterate through the heights. For each height, use binary search to find its position in the current LIS array.
   • If the height is greater than all elements, append it to the array. Otherwise, replace the first element in the array that is greater than or equal to the height.
4. Return the length: The size of the LIS array at the end is the maximum number of envelopes you can nest.

This approach is efficient and leverages classic LIS optimization techniques.

Example Walkthrough

Let's consider the sample input: [[5,4],[6,4],[6,7],[2,3]]

1. Sort envelopes: After sorting by width ascending and height descending, we get: [[2,3],[5,4],[6,7],[6,4]]
2. Extract heights: The heights array is [3,4,7,4]
3. Find LIS:
   • Start with empty dp=[]
   • 3: Insert at position 0 → dp=[3]
   • 4: Insert at position 1 → dp=[3,4]
   • 7: Insert at position 2 → dp=[3,4,7]
   • 4: Replace at position 1 (since 4 is not greater than 4) → dp=[3,4,7]
4. Result: The length of dp is 3, so the answer is 3.

This means the maximum number of envelopes that can be nested is 3.

Time and Space Complexity

• Brute-force approach: Tries all possible sequences, which is factorial time: O(n!). This is impractical for large inputs.
• Optimized approach:
  • Sorting takes O(n log n) time.
  • The LIS step (with binary search) is O(n log n).
  • Total time complexity: O(n log n)
  • Space complexity: O(n), for storing the heights and the LIS array.

Summary

The Russian Doll Envelopes problem is a clever variation of the Longest Increasing Subsequence, but in two dimensions. By sorting envelopes by width (and height in reverse for ties), we transform the problem into a classic LIS challenge. Using binary search, we achieve an efficient O(n log n) solution. The key insight is the sorting strategy, which elegantly handles the two-dimensional nesting constraint and simplifies the problem into a manageable form.