class Solution { public class pair implements Comparable<pair>{ int width , height ; pair(){ } pair(int width , int height){ this.width = width ; this.height = height; } //this - other = ascending order , other-this = descending order public int compareTo(pair o){ //if width are equal sort based on hieghts if(this.width == o.width) return this.height - o.height; //else sort based on width only else return this.width - o.width; } } public int maxEnvelopes(int[][] envelopes) { /* similiar to max overlapping bridges , LIS concept will be used here approach - sort on the bases of either width or height lets take width for eg: now you already have width in ascending order , now find LIS of height for every width , maximum of these will be your answer ** sorting width makes sure that you get width in ascending order and finding LIS of heights makes sure no hieghts overlap to each other and you can find Maximum LIS of heights which will become you answer */ //making a pair class array to store heights and width of each envelops pair[] arr = new pair[envelopes.length]; //taking input in the pair array int i = 0; for(int input[] : envelopes){ arr[i] = new pair(); //initializing the object arr[i].width = input[0]; arr[i].height = input[1]; i++; } //sorting the pair array based on width Arrays.sort(arr); //calling LIS function based on height for all sorted widths in pair array return LIS(arr); } public int LIS(pair[] arr){ int n = arr.length ; int[] LIS = new int[n]; LIS[0] = 1; //for the first envelop it can only make 1 LIS of envelopes int ans = 1; //traversing all the sorted widths envelops for(int i = 1 ; i < n ;i++ ){ //checking all envelops before current which have smaller height and for those //which dont have their widths equal as it is mentioned in the question for(int j = i-1 ; j >= 0 ; j--){ if(arr[j].width != arr[i].width && arr[j].height < arr[i].height) LIS[i] = Math.max(LIS[i],LIS[j]); } //adding LIS for current element LIS[i]+=1; ans = Math.max(ans , LIS[i]); } return ans; } }