Q13 Russian Doll Envelopes - LeetCode 354 solution1(LIS in O(n^2))

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;
    }
}