class Solution { public int maxEnvelopes(int[][] envelopes) { /* Q13 of dp playlist , the question is reducable to LIS , we sort the array based on width now we have sorted width so we find LIS on heights its very important to sort the heights in descending order if widths are equal as its given that , widths and heights both should be strictly greater */ int n = envelopes.length; /* sorting the enevelopes array based on width , we use thiss and otherr as we cannot use legacy naming this and other , we sort the array based on width and if widths are equal we sort them based on descending heights */ Arrays.sort(envelopes , new Comparator<int []>(){ public int compare(int thiss[] , int otherr[]){ if(thiss[0] == otherr[0]) return otherr[1] - thiss[1]; else return thiss[0] - otherr[0]; } }); /* we initialise the dp array with MAX_VALUE , then traverse the array and keep placing elements based on patience sort or deck of cards , every cell in dp denotes last element of ith LIS , we find position of new values using upperbound and keep updating the ith index which stores last element for ith index. */ int[] dp = new int[n]; Arrays.fill(dp , Integer.MAX_VALUE); for(int i = 0 ;i < dp.length ; i++){ int idx = upperBound(dp , 0 , i ,envelopes[i][1]); dp[idx] = envelopes[i][1]; } //traverse reversely and find the first not intmax value which is our LIS for(int i = n-1 ; i>=0 ; i--){ if(dp[i] != Integer.MAX_VALUE){ return i+1; } } return -1; //would never reach this statement } //function to find just greater or equal to index public int upperBound(int[] dp , int low , int high , int target){ while(low <= high){ int mid = low + (high - low)/2; if(dp[mid] == target) return mid; else if(dp[mid] > target) high = mid-1; else low = mid+1; } return low; } }