✅ JAVA | SORTING + LIS | TLE | MLE | O(N^2) | O(N LOGN) | 👍🏼 |
COUPLE OF SOLUTIONS IN JAVA\n Below is Naive approach which throws TLE.\n \nclass Solution {\n    \n    private int MAX_VALUE = 100002;\n        \n    public in
__COUPLE OF SOLUTIONS IN JAVA__\n* Below is Naive approach which throws TLE.\n ```\nclass Solution {\n    \n    private int MAX_VALUE = 100002;\n        \n    public int maxEnvelopes(int[][] envelopes) {\n        Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);\n        int[] prev = new int[]{MAX_VALUE, MAX_VALUE};\n        return LIS(envelopes, envelopes.length - 1, prev);\n    }\n    \n    private int LIS(int[][] envelopes, int index, int[] prev){\n        if(index == 0){\n            return (envelopes[0][0] < prev[0] && envelopes[0][1] < prev[1]) ? 1 : 0;\n        }\n        int exclude = LIS(envelopes, index - 1, prev);\n        int include = 0;\n        if(envelopes[index][0] < prev[0] && envelopes[index][1] < prev[1]){\n            include = 1 + LIS(envelopes, index - 1, envelopes[index]);\n        }\n\n        return Math.max(exclude, include);\n    }\n}\n ```\n * Below is Memoized approach which  throws MLE.\n ```\n class Solution {\n    \n    private int MAX_VALUE = 100002;\n        \n    public int maxEnvelopes(int[][] envelopes) {\n        Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);\n        int[] prev = new int[]{MAX_VALUE, MAX_VALUE};\n        int[][][] dp = new int[envelopes.length][MAX_VALUE + 1][MAX_VALUE + 1];\n        \n        for(int[][] grid : dp)\n            for(int[] row : grid)\n                Arrays.fill(row, -1);\n        \n        return LIS(envelopes, envelopes.length - 1, prev, dp);\n    }\n    \n    private int LIS(int[][] envelopes, int index, int[] prev, int[][][] dp){\n        if(index == 0){\n            return (envelopes[0][0] < prev[0] && envelopes[0][1] < prev[1]) ? 1 : 0;\n        }\n        \n        if(dp[index][prev[0]][prev[1]] != -1) return dp[index][prev[0]][prev[1]];\n        int exclude = LIS(envelopes, index - 1, prev, dp);\n        int include = 0;\n        if(envelopes[index][0] < prev[0] && envelopes[index][1] < prev[1]){\n            include = 1 + LIS(envelopes, index - 1, envelopes[index], dp);\n        }\n\n        return dp[index][prev[0]][prev[1]] = Math.max(exclude, include);\n    }\n \n}\n ```\n * Below is Optmized approach which must pass all cases but sadly passes oly 85/87 TC and also throws TLE\uD83E\uDD72.\n ```\n class Solution {\n    \n    private int MAX_VALUE = 100002;\n        \n    public int maxEnvelopes(int[][] envelopes) {\n        int n = envelopes.length, maxNumberOfEnvelopes = 1;\n        \n        // We sort According to Width!!\n        Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);\n        \n        for(int[] envelope : envelopes)\n            System.out.println(envelope[0] + " " + envelope[1]);\n        \n        // We find LIS according to Height!!\n        int prev = MAX_VALUE;\n        int[] dp = new int[n + 1];\n        dp[0] = 1;\n        \n        for(int i = 1;i < n; i++){\n            dp[i] = 1;\n            for(int j = 0; j < i; j++)\n                if(envelopes[i][0] != envelopes[j][0] && envelopes[i][1] > envelopes[j][1])\n                    dp[i] = Math.max(dp[i], dp[j] + 1);\n            \n            maxNumberOfEnvelopes = Math.max(maxNumberOfEnvelopes, dp[i]);\n        }\n        \n       return maxNumberOfEnvelopes;\n    }\n \n}\n```\n\n* Below is the Optmized Solution which passes all test cases with TC O(N logN).\uD83E\uDEE1\n```\nclass Solution {\n        \n    public int maxEnvelopes(int[][] envelopes) {\n        int n = envelopes.length, len = 0;\n        \n        // We sort According to Width!!\n        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);\n        \n        int dp[] = new int[n];\n        for(int[] envelope : envelopes){\n            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);\n            if(index < 0)\n                index = -(index + 1);\n            dp[index] = envelope[1];\n            if(index == len)\n                len++;\n        }\n\t\t\n        return len;\n    }   \n}\n```\n \n * Bonus Tip :: Always make helper functions as private[ABSTRACTION].\n * Happy Coding and do Upvote if Helpful!\n \n author : [@bharathkalyans](https://leetcode.com/bharathkalyans/)\nlinkedin : [@bharathkalyans](https://www.linkedin.com/in/bharathkalyans/)\ntwitter : [@bharathkalyans](https://twitter.com/bharathkalyans)\ngithub : [@bharathkalyans](https://github.com/bharathkalyans/)\n \n
['Dynamic Programming', 'Binary Tree', 'Java']