Last updated on July 21st, 2024 at 04:32 am

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

Topics

Binary Search, Dynamic Programming

Companies

Google

Level of Question

Hard

Russian Doll Envelopes 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

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();
    }
};

2. 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()){
                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. 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
};

4. 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)