Last updated on January 17th, 2025 at 01:05 am
Here, we see a Russian Doll Envelopes LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Level of Question
Hard
Russian Doll Envelopes LeetCode Solution
Table of Contents
1. Problem Statement
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
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
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Modified Binary Search”. The problem involves sorting the envelopes and then finding the Longest Increasing Subsequence (LIS) of the heights using a binary search approach. This is a classic example of applying binary search in a modified way to optimize the LIS computation.
3. Code Implementation in Different Languages
3.1 Russian Doll Envelopes C++
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
ios::sync_with_stdio(false);
int size = envelopes.size();
if (size == 0) {
return 0;
}
sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
});
vector<int> dp;
for (int i = 0; i < size; i++) {
auto it = lower_bound(dp.begin(), dp.end(), envelopes[i][1]);
if (it == dp.end()) {
dp.push_back(envelopes[i][1]);
} else {
*it = envelopes[i][1];
}
}
return dp.size();
}
};
3.2 Russian Doll Envelopes Java
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
else {
return a[0] - b[0];
}
});
int nums[]=new int [envelopes.length];
int j=0;
for(int i=0;i<envelopes.length;i++){
nums[j]=envelopes[i][1];
j++;
}
return lengthOfLIS(nums);
}
public int lengthOfLIS(int[] nums) {
ArrayList<Integer> al=new ArrayList<>();
for(int i=0;i<nums.length;i++){
int index=binary(al,nums[i]);
if(index==al.size()){
al.add(nums[i]);
}
else{
al.set(index,nums[i]);
}
}
return al.size();
}
public int binary(ArrayList<Integer> al,int target){
int s=0;
int e=al.size();
int result=al.size();
while(s<e){
int mid=(s+e)/2;
if(al.get(mid)<target){
s=mid+1;
}
else{
e=mid;
result=mid;
}
}
return result;
}
}
3.3 Russian Doll Envelopes JavaScript
var maxEnvelopes = function(envelopes) {
envelopes.sort((a,b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])
let len = envelopes.length, dp = []
for (let i = 0; i < len; i++) {
let height = envelopes[i][1], left = 0, right = dp.length
while (left < right) {
let mid = (left + right) >> 1
if (dp[mid] < height) left = mid + 1
else right = mid
}
dp[left] = height
}
return dp.length
};
3.4 Russian Doll Envelopes Python
class Solution(object):
def maxEnvelopes(self, envelopes):
envelopes.sort(key=lambda x: (x[0], -x[1]))
dp = []
for _,height in envelopes:
left = bisect_left(dp, height)
if left == len(dp): dp.append(height)
else: dp[left] = height
return len(dp)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log n) | O(n) |
| Java | O(n log n) | O(n) |
| JavaScript | O(n log n) | O(n) |
| Python | O(n log n) | O(n) |
- Sorted the envelopes by width (ascending) and height (descending for ties).
- Uses a DP array to find the LIS of the heights using binary search.
- The size of the DP array at the end gives the maximum number of envelopes that can be nested.