354. Russian Doll Envelopes – Leetcode Solutions

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Step 1: Sort the envelopes
        # Sort by width in ascending order; if widths are the same, sort by height in descending order
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        
        # Step 2: Extract the heights of the sorted envelopes
        heights = [envelope[1] for envelope in envelopes]
        
        # Step 3: Find the length of LIS in the heights
        # This will store the current longest increasing subsequence of heights
        lis = []
        
        for h in heights:
            # Find the position where h can be placed (or replace an existing element)
            pos = bisect_left(lis, h)
            
            # If pos is equal to the length of lis, it means h is larger than any element in lis
            if pos == len(lis):
                lis.append(h)  # Add h to the end of the lis
            else:
                lis[pos] = h  # Replace the element at pos with h
        
        # The length of the lis array is the maximum number of envelopes we can Russian doll
        return len(lis)

class Solution {
public:
    // Function to calculate the maximum number of envelopes that can be Russian-dolled.
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // Step 1: Sort the envelopes based on width.
        // If two envelopes have the same width, sort them in decreasing order of height.
        // This helps in ensuring that envelopes with the same width do not interfere with the Russian Doll process.
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) {
                return a[1] > b[1]; // Sort by decreasing height if width is the same
            } else {
                return a[0] < b[0]; // Sort by increasing width otherwise
            }
        });

        // Step 2: Create a vector to store the heights of envelopes that can be nested.
        // After sorting the envelopes by width, we only need to focus on the heights.
        // We can apply a variant of the Longest Increasing Subsequence (LIS) on the heights to solve this.
        vector<int> dp;  // This will store the heights in the current possible sequence

        // Step 3: Apply Longest Increasing Subsequence on heights
        for (auto& envelope : envelopes) {
            int height = envelope[1];
            // Find the position in 'dp' where 'height' should be placed (using binary search).
            auto it = lower_bound(dp.begin(), dp.end(), height);
            
            if (it == dp.end()) {
                // If the height is greater than all elements in dp, append it to dp.
                dp.push_back(height);
            } else {
                // Otherwise, replace the element at the found position with this height
                // to keep the sequence as small as possible.
                *it = height;
            }
        }

        // Step 4: The size of 'dp' will be the maximum number of envelopes we can Russian doll.
        return dp.size();
    }
};

var maxEnvelopes = function(envelopes) {
    // Step 1: Sort the envelopes.
    // Sort by width in ascending order, and if two widths are the same, sort by height in descending order.
    envelopes.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1]; // For same width, sort by height descending.
        } else {
            return a[0] - b[0]; // Otherwise, sort by width ascending.
        }
    });

    // Step 2: Extract the heights (second element of each pair) after sorting.
    let heights = envelopes.map(envelope => envelope[1]);

    // Step 3: Find the length of the longest increasing subsequence (LIS) of heights.
    // To do this, we'll maintain an array `lis` where we apply a binary search approach.
    let lis = [];

    for (let height of heights) {
        // Find the insertion position using binary search.
        let left = 0, right = lis.length;

        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (lis[mid] < height) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // If the current height is greater than all elements in `lis`, append it.
        // Otherwise, replace the element at the found position with the current height.
        if (left === lis.length) {
            lis.push(height);
        } else {
            lis[left] = height;
        }
    }

    // The length of the `lis` array gives the maximum number of envelopes that can be Russian-dolled.
    return lis.length;
};

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // Step 1: Sort the envelopes
        // First, sort envelopes by width (wi) in ascending order.
        // If two envelopes have the same width, then sort them by height (hi) in descending order.
        // This prevents envelopes with the same width but different heights from being placed within each other.
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1]; // If widths are the same, sort by height in descending order
            }
            return a[0] - b[0]; // Otherwise, sort by width in ascending order
        });

        // Step 2: Apply Longest Increasing Subsequence (LIS) on heights
        // Now, we need to find the longest increasing subsequence (LIS) on the heights (hi).
        // The reason we sort by width first and then apply LIS on height is to ensure
        // that for any two envelopes, either one can be nested in the other or not.

        // Create an array (or a list) to store the heights for the LIS calculation.
        int[] dp = new int[envelopes.length];
        int length = 0;

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

            // Step 3: Binary search for the correct position of the current height in the dp array.
            // We use binary search to either replace an existing element in dp (to maintain
            // the smallest possible tail element for a sequence of the same length) or to extend the dp array.
            int idx = Arrays.binarySearch(dp, 0, length, height);

            // If the binary search returns a negative index, it indicates the position where the current
            // height should be inserted. Binary search in Java returns (-(insertion point) - 1),
            // so we use -idx - 1 to get the correct insertion point.
            if (idx < 0) {
                idx = -idx - 1;
            }

            // Step 4: Insert or replace the element in the dp array.
            dp[idx] = height;

            // If the index is equal to the current length of the dp array, it means we are extending
            // the length of the sequence.
            if (idx == length) {
                length++;
            }
        }

        // Step 5: Return the length of the longest increasing subsequence,
        // which corresponds to the maximum number of envelopes that can be Russian dolled.
        return length;
    }
}