Leetcode 354. Russian Doll Envelopes

Problem Explanation:

Given a list of envelopes represented as pairs of integers [width, height], our task is to put one envelope inside another to form a "Russian Doll" structure. An envelope (i, j) can fit inside another (i', j') only if both the width (i') and height (j') of the latter is strictly greater than the width (i) and height (j) of the former. Importantly, rotation is not allowed, meaning you cannot consider flipping an envelope - the width always remains width, and the height always remains height. The problem is to figure out the maximum number of envelopes that can be nested within each other following these rules.

This problem can be approached as a variant of the "Longest Increasing Subsequence" (LIS) problem, and can be resolved using a dynamic programming solution or binary search.

Walkthrough

Let's take an example where the input is: [[5,4],[6,4],[6,7],[2,3]]. In the first step, the envelopes are sorted based on their increasing width and decreasing height if their width are the same. After sorting, the envelopes are: [[2,3],[5,4],[6,7], [6,4]]. Now, we find the longest increasing subsequence based on the heights of the envelopes. We initialize the answer (maxEnvelopes) to 0 and create an empty array dp of size n (which is the number of envelopes). We then iteratively process each envelope's height. For each height, we perform a binary search in the dp array to find the appropriate position for the current height (in our ascending sequence). The position found serves as our index in the dp array, where we can replace the current value with the envelope's height. If the index is the same as our current maximum count of envelopes, we increase the count. Finally, our function returns the maximum count of envelopes.

Solution:

Python

1
2python
3class Solution:
4    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
5        if not envelopes:
6            return 0
7
8        # Sort envelopes by width in ascending order and by height in descending order when widths are the same
9        # This is done to ensure that envelopes with the same width are not considered as part of the increasing subsequence of heights
10        envelopes.sort(key=lambda x: (x[0], -x[1]))
11
12        dp = []
13        for _, h in envelopes:
14            idx = bisect_left(dp, h)
15            if idx == len(dp):
16                dp.append(h)
17            else:
18                dp[idx] = h
19
20        return len(dp)

Java

1
2java
3class Solution {
4    public int maxEnvelopes(int[][] envelopes) {
5        if (envelopes == null || envelopes.length == 0 
6           || envelopes[0] == null || envelopes[0].length != 2)
7            return 0;
8        Arrays.sort(envelopes, new Comparator<int[]>() {
9            public int compare(int[] arr1, int[] arr2) {
10                if (arr1[0] == arr2[0])
11                    return arr2[1] - arr1[1];
12                else
13                    return arr1[0] - arr2[0];
14           }
15        });
16        int dp[] = new int[envelopes.length];
17        int len = 0;
18        for(int[] envelope : envelopes) {
19            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
20            if(index < 0)
21                index = -(index + 1);
22            dp[index] = envelope[1];
23            if (index == len)
24                len++;
25        }
26        return len;
27    }
28}

C++

1
2c++
3class Solution {
4public:
5    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
6        sort(envelopes.begin(), envelopes.end(), 
7        [](pair<int,int>& a, pair<int,int>& b) {  // sort width in ascending order and height in descending order for same width 
8            return a.first < b.first || (a.first == b.first && a.second > b.second); 
9        });  
10        vector<int> dp;
11        for (auto& envelope : envelopes) {
12            auto it = lower_bound(dp.begin(), dp.end(), envelope.second); // binary search in dp
13            if (it == dp.end()) dp.push_back(envelope.second);
14            else *it = envelope.second; 
15        }
16        return dp.size();
17    }
18};

JavaScript

1
2javascript
3var maxEnvelopes = function(envelopes) {
4    if(envelopes.length === 0) return 0;
5
6    envelopes.sort((a,b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
7
8    let dp = [envelopes[0][1]];
9    
10    for(let i = 1; i < envelopes.length; i++){
11        if(dp[dp.length - 1] < envelopes[i][1]){
12            dp.push(envelopes[i][1]);
13        }else{
14            let left = 0;
15            let right = dp.length - 1;
16
17            while(left < right){
18                let mid = Math.floor(left + (right - left) / 2);
19                if(dp[mid] < envelopes[i][1]){
20                    left = mid + 1;
21                }else{
22                    right = mid;
23                }
24            }
25            dp[left] = envelopes[i][1];
26        }
27    }
28    
29    return dp.length;
30};

C#

1
2csharp
3public class Solution {
4    public int MaxEnvelopes(int[,] envelopes) {
5        if(envelopes == null || envelopes.GetLength(0) == 0 || envelopes.GetLength(1) != 2)
6            return 0;
7        int n = envelopes.GetLength(0);
8        int[][] arr = new int[n][];
9        for(int i = 0; i < n; i++)
10            arr[i] = new int[]{envelopes[i, 0], envelopes[i, 1]};
11        Array.Sort(arr, new Comparison<int[]>(
12            (a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
13        int[] dp = new int[n];
14        int len = 0;
15        foreach(int[] envelope in arr) {
16            int i = Array.BinarySearch(dp, 0, len, envelope[1]);
17            if(i < 0)
18                i = -(i + 1);
19            dp[i] = envelope[1];
20            if(i == len)
21                len++;
22        }
23        return len;
24    }
25}

In all solutions, we start by sorting the input array of envelopes based on a specific condition which compares the width and height. After the sorting, we initialize an empty dp list which will contain the longest increasing subsequence of heights. Using a binary search, we determine the correct position of each height in the dp array. To finish, we return the number of envelopes that can be nested which is the length of the dp list.### Time Complexity Analysis

The time complexity of this solution is primarily determined by the sorting operation and the binary search operation.

Sorting the array of envelopes has a time complexity of O(n log n), where n is the number of envelopes.

The binary search operation happens inside a loop that runs through all the envelopes, which would normally suggest a time complexity of O(n log n). However, as the binary search itself takes O(log n) time and it is performed n times, this does not change the overall time complexity.

Thus, the overall time complexity of this problem is O(n log n).

Space Complexity Analysis

The space complexity is determined by the additional space required which is the space for the dp array. In the worst case, all envelopes can be put one inside another, so the space complexity is O(n), where n is the number of envelopes.

Conclusion

In conclusion, these solutions to the Russian Doll Envelopes problem effectively utilize the concept of binary search and dynamic programming. Importantly, while the problem might seem complex at an initial glance, recognizing its similarity to the popular LIS problem can allow for an efficient and elegant solution. As is often the case with complex coding problems, the key is to break it down into smaller, more manageable parts that you are familiar with handling.

The Python, Java, C++, JavaScript, and C# implementations provided here solve the problem in a similar manner and offer a good example of how the same solution can be expressed in different programming languages. Understanding these solutions will not only help with similar problems but also enhance your overall algorithms and data structures skills, which are essential for any software developer or data scientist.