Q13 Russian Doll Envelopes - LeetCode 354 ( LIS -> O(nlogn) solution)

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