Leetcode Russian Doll Envelopes problem solution

In this Leetcode Russian Doll Envelopes problem solution, You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represent 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).

Problem solution in Python.

class Solution:
    def maxEnvelopes(self, A: List[List[int]]) -> int:
        A.sort(key=lambda x: (x[0], -x[1]))
        tails = [inf] * len(A)
        size = 0
        for w in map(lambda x: x[1], A):
            i = bisect_left(tails, w)
            tails[i] = w
            size = max(i + 1, size)
        return size

Problem solution in Java.

class Solution {
    private Map<Long, Integer> map = new HashMap<>();
    public int maxEnvelopes(int[][] envelopes) {
        return dfs(envelopes, new int[]{-1, -1});
    }
    private int dfs(int[][] envelopes, int[] curr) {
        long key = (curr[0] + curr[1]) * (curr[0] + curr[1] + 1) / 2 + curr[1];
        if(map.containsKey(key)) return map.get(key);
        int res = Integer.MIN_VALUE;
        for(int[] e : envelopes) {
            if(e[0] > curr[0] && e[1] > curr[1]) {
                res = Math.max(res, dfs(envelopes, e));
            }
        }
        if(res == Integer.MIN_VALUE) {
            res = 0;
        }else {
            res++;
        }
        map.put(key, res);
        return res;
    }
}

Problem solution in C++.

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& a) {
        int n=(int)a.size();
        assert(n>0);
        vector<int>dp;
        sort(a.begin(),a.end(),[&](vector<int>&x,vector<int>&y){
            return x[0]<y[0] || (x[0]==y[0] && x[1]>y[1]); 
        });
        dp.emplace_back(a[0][1]);
        for(int i=1;i<n;++i){
            int cur_height=a[i][1];
            auto it=lower_bound(dp.begin(),dp.end(),cur_height);
            if(it==dp.end())
                dp.emplace_back(cur_height);
            else if(*it>cur_height)
                dp[it-dp.begin()]=cur_height;
        }
        return dp.size();
    }
};

coding problems