Java: Longest Increasing Subsequence

Thought Process

The Longest Increasing Subsequence problem requires finding the length of the longest subsequence in an array where the elements are in increasing order. Here are two approaches:

Approach 1: Dynamic Programming - Use a LIS array to store the length of the longest increasing subsequence ending at each index. For each element, compare it with all previous elements. If the current element is greater, update the LIS value. Finally, track the maximum value in the LIS array to get the result.

Approach 2: Binary Search with Patience Sorting - Maintain a subsequence array to store the smallest possible tail value. While iterating, use lower_bound to find the position of the current element in the subsequence array. If the element is greater than the last element, append it. Otherwise, replace the element at the found position.

Approach 1: Dynamic Programming 

class Solution {
    public int lengthOfLIS(int[] nums) {
        
        int sz = nums.length;
        int[] LIS = new int[sz];
        int lengthOfLIS = 1;
        
        Arrays.fill(LIS,1);
        for(int i=1;i<sz;i++){
            for(int j=0;j<i;j++){

                if(nums[j] < nums[i])
                    LIS[i] = Math.max(LIS[i],LIS[j]+1);
            }
            lengthOfLIS = Math.max(lengthOfLIS, LIS[i]);
        }
        return lengthOfLIS;
    }
}

Approach 2: Binary Search with Patience Sorting 

class Solution {
    public int lengthOfLIS(int[] nums) {
        
        List<Integer> subsequence = new ArrayList<>();
        int sz = nums.length;

        subsequence.add(nums[0]);
        for(int i=1;i<sz;i++){

            // If nums[i] is greater than last element of subsequence than it will help to create
            // longer increasing subsequence. So, add it in our list.
            if(nums[i]>subsequence.get(subsequence.size()-1)){
                subsequence.add(nums[i]);
            }
            else{

                // we want to find the index of element in subsequence which is greater than 
                // or equal to nums[i] and then replace that element with nums[i]
                int x = Collections.binarySearch(subsequence,nums[i]);
                if(x<0)
                    x = Math.abs(x)-1; // This will the index of upper bound of nums[i]
                
                subsequence.set(x,nums[i]);
            }
        }
        return subsequence.size();
    }
}

Code Complexity

Time Complexity: O(n2) & O(n log n)

Approach 1 uses nested loops, resulting in quadratic time complexity. Approach 2 uses binary search, reducing the time complexity to O(n log n).

Space Complexity: O(n)

Both approaches use additional space proportional to the input size.

Code copied!