Russian Doll Envelopes

XXX. Russian Doll Envelopes

Dynamic Programming

Binary Search

Sorting

Problem Statement:

You are given a list of envelopes, where each envelope is represented as a pair of integers [width, height]. The goal is to find the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

An envelope can fit inside another if and only if both the width and height of one envelope are strictly smaller than the width and height of the other envelope.

Algorithm:

1. Check for invalid input and return 0 if the input is invalid.
2. Sort the envelopes by width in ascending order. If two envelopes have the same width, sort by height in descending order.
3. Apply the Longest Increasing Subsequence (LIS) algorithm on the heights of the sorted envelopes using binary search for optimization:
• Maintain a dynamic array to track the LIS.
• For each envelope height, use binary search to determine its position in the LIS array.
• If the height can extend the LIS, add it to the array. Otherwise, replace the existing value in the LIS array.
4. Return the length of the LIS array as the result.

Complexity:

Time Complexity: O(n log n), where n is the number of envelopes.
Space Complexity: O(n), for the LIS array.

Java Implementation:

import java.util.*;

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // Step 1: Handle edge cases where input is invalid
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length != 2) return 0;

        // Step 2: Sort the envelopes
        // Use lambda comparator: sort by width ascending; if widths are equal, sort by height descending
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

        // Step 3: Use DP and Binary Search to find the LIS of heights
        int[] dp = new int[envelopes.length]; // DP array to store the LIS of heights
        int len = 0; // Length of the LIS

        for (int[] envelope : envelopes) {
            int height = envelope[1]; // Current envelope height

            // Perform binary search to find the insertion point in dp array
            int index = Arrays.binarySearch(dp, 0, len, height);
            if (index < 0) index = -(index + 1); // Convert negative index to insertion point

            dp[index] = height; // Update the dp array with the current height

            // If the height is added at the end, increase the LIS length
            if (index == len) len++;
        }

        return len; // The length of the LIS is the result
    }
}

Python Implementation:

import bisect

def maxEnvelopes(envelopes):
    # Step 1: Handle edge cases where input is invalid
    if not envelopes or not envelopes[0] or len(envelopes[0]) != 2:
        return 0

    # Step 2: Sort the envelopes
    # Sort by width ascending; if widths are equal, sort by height descending
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # Step 3: Use DP and Binary Search to find the LIS of heights
    dp = []  # DP array to store the LIS of heights

    for _, height in envelopes:
        # Perform binary search to find the insertion point in dp array
        index = bisect.bisect_left(dp, height)

        if index == len(dp):
            dp.append(height)  # Extend the LIS
        else:
            dp[index] = height  # Update the dp array with the current height

    return len(dp)  # The length of the LIS is the result

C++ Implementation:

#include 
#include 
using namespace std;

int maxEnvelopes(vector>& envelopes) {
    // Step 1: Handle edge cases where input is invalid
    if (envelopes.empty() || envelopes[0].size() != 2) return 0;

    // Step 2: Sort the envelopes
    // Sort by width ascending; if widths are equal, sort by height descending
    sort(envelopes.begin(), envelopes.end(), [](vector& a, vector& b) {
        return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
    });

    // Step 3: Use DP and Binary Search to find the LIS of heights
    vector dp;  // DP array to store the LIS of heights

    for (auto& envelope : envelopes) {
        int height = envelope[1];  // Current envelope height

        // Perform binary search to find the insertion point in dp array
        auto it = lower_bound(dp.begin(), dp.end(), height);

        if (it == dp.end()) {
            dp.push_back(height);  // Extend the LIS
        } else {
            *it = height;  // Update the dp array with the current height
        }
    }

    return dp.size();  // The length of the LIS is the result
}