354. Russian Doll Envelopes

Published on February 4, 2024

Question

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

Constraints:

1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

Approach

2-d version of longest subsequence ,however, same approach will cause TLE.(O(n*n))
So we might need to turn to O(n*logn); that is we leverage binary search in the middle of searching some elements.
1. You maintain a result array of envelope, if the w and h of envelope[i] are lager then the last element in this array, then we append this envelope;
2. Other wise we replace the larger one in the res array with it.
3. Here the look up implementation can leverage binary search which will optimize the time complexity.
4. Check out the official solution for detailed explanation and the tricks.

Code(TLE)

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = dp[0];
        for (int i = 1; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

Code2

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0]) {
                    return arr2[1] - arr1[1];
                } else {
                    return arr1[0] - arr2[0];
                }
           }
        });
        List<int[]> list = new ArrayList<>();
        int[] secondDim = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            secondDim[i] = envelopes[i][1];
        }
        return LenOfLIS(secondDim);
    }
    
    private int LenOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = binarySearch(dp, 0, len, num);
            if (i < 0) i = -(i = 1);
            dp[i] = num;
            if (i == len) len++;
        }
        return len;
    }
    
    public int binarySearch(int[] dp, int start, int end, int target) {
       
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target < dp[mid]) {
                end = mid;
            } else if (target > dp[mid]) {
                start = mid;
            } else {
                return mid;
            }
        }
        if (dp[start] >= target) return start;
        return end;
    }
}