# Russian Doll Envelopes LeetCode Solution

Here, We see Russian Doll Envelopes LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## 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

## Russian Doll Envelopes LeetCode Solution 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();
}
};```Code language: PHP (php)```

## Russian Doll Envelopes LeetCode Solution 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()){
}
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;
}
}    ```Code language: PHP (php)```

## Russian Doll Envelopes Solution 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
};```Code language: JavaScript (javascript)```

## Russian Doll Envelopes Solution 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)``````
Scroll to Top