# 354. Russian Doll Envelopes

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgYiy0BDiUsrW8X6K98%2F-MgYjX8L0OH-JgouQk7j%2Fimage.png?alt=media\&token=07c65759-d3b4-4006-9940-6d511f48e2c3)

## idea - sort w by asc first, but when w are the same, h do sort by desc, the focus on h find the LIS (leetcode 300)

## when widths are the same, why height should do sort by desc?

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MgQlieDgNR5Kq25Opbw%2F-MgYiebDyTAdYS0LOU_k%2Fimage.png?alt=media\&token=2e186dfb-f6a1-4d80-8b94-7a074e7dcba7)

**簡而言之 就是為了對 h 做 LIS 找到最後的答案, 所以 w 一樣時, h 要做 desc 不然因為 LIS 是 asc 的 => 會錯**

## sort + DP + binary search

```java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // sort width first small to large, if width is the same, height pick larger one
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        
        int[] tails = new int[envelopes.length];
        int res = 0;
        for(int envelope[] : envelopes) {
            int i = binarySearch(tails, res, envelope[1]); // for height to do the 300. Longest Increasing Subsequence
            tails[i] = envelope[1];
            if(res == i) res++;

        }
        return res;
    }
    private int binarySearch(int tails[], int res, int num) {
        int i = 0, j = res;
        while(i < j) {
            int m = (i + j) / 2;

            if(tails[m] < num) {
                i = m + 1;

            } else {
                j = m;

            }
        }
        return i;
    }
}
```



O(n^2) TLE

````java
```java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; 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 result = 0;
        for (int i = 0; i < n; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}
```
````
