Leetcode — 300. Longest Increasing Subsequence

The link to the problem: https://leetcode.com/problems/longest-increasing-subsequence/

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Thoughts:

My first thought is that it is a good idea to use dynamic programming to solve this problem. The reason is that since we only need to return the length of the longest increasing subsequence, we don’t really need to know the actual numbers in the subsequence. We only need to know that it will always valid if we decide to add a number to extend a certain increasing subsequence.

⚠️There is only one condition if we want to add a number into an increasing subsequence- as long as the value of the new number is larger than the biggest number in the current subsequence since the new number will always be placed into the subsequence.

Hence, if we want to find the longest length of the increasing subsequence which includes the current number as the last element, we need to refer to the longest lengths in all the previous positions. We can use a dp array to store those longest lengths and help us save some work. dp[i] represents the longest length of the increasing subsequence we can find when nums[i] is the largest number in the subsequence.

Since we always need to check all previous positions to see if we can “take a ride” to expand their longest subsequence, the time complexity will be O(n²)

Below is the 58ms code that beats 49%-

public int lengthOfLIS(int[] nums) {
        int max = 1;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j] < nums[i])
                    dp[i] = Math.max(dp[i],dp[j]+1);
            }
            if(dp[i]>max)
                max = dp[i];
        }
        return max;
    }

Follow Up: Could you improve it to O(n log(n)) time complexity?

When you are happy about how you solve this problem using dynamic programming, the interviewer will ask you this follow up question. Let’s see if there’s any way to solve this problem more efficiently.

Every time when we are finding the longest length for position i, we need to check every position before i and see if we can add nums[i] into their longest increasing subsequences that ends in nums[j]. This is actually wasting time since we cannot know the longest length until we really find the applicable longest increasing subsequence.

Code Logic:

This time instead of using an array to store the longest length for each position, we use an array named arr to store several increasing numbers, and a variable named len to record the length of arr.
(i.e., arr[0] ~ arr[len-1] stores a series of increasing numbers. Positions after len haven’t included any number yet and are waiting for us to add new numbers that are greater than arr[len-1] )

We will traverse every number in the given array nums. We will use Binary Search (Time complexity: O(lg(n))) to find the position to place the current number into the array arr. When we found that the current number is bigger than all the numbers in arr, it means we can expand the length of the longest increasing subsequence and update the variable len.

⚠️One important thing is that the numbers in the array don’t mean they are actually the longest increasing subsequence! We only know that,

1. All the numbers are sorted in increasing order, but they are not guaranteed to be a valid subsequence. For example, although arr[0] < arr[1], it is possible that arr[0] appears later than arr[1] in nums.
2. When the longest length is updated, we only know the current number nums[i] is the last number of this longest increasing subsequence. We only know there are total (len-1) numbers in arr are lesser than nums[i], and these numbers can form a valid subsequence. (i.e., the valid subsequence might or might not are the current numbers we can see in arr[0]~ arr[len-2], only arr[len-1] = nums[i] is for sure)
3. The length variable represents the longest length of the increasing subsequence that we can find so far.

😕: How can we know the length is correct while we can’t really tell the numbers in the longest subsequence?

What we do in every iteration is trying to place the current number nums[i] into arr. The best situation we want to see is that the current number is larger than all the numbers in arr, and we need to place the current number at the end of the array. However, we won’t always be that lucky. If the current number cannot be placed at the end of the array, the number that is bigger than nums[i] and also the closest number with it will be replaced by nums[i]. One benefit is that the numbers in arr are getting smaller while also remaining the longest length, this means that it is easier to get a new number that is bigger than all other numbers and we can expand our longest length.

👷Let’s use the example below to see how we update arr.
Assume nums = [10, 9, 2, 5, 3, 7, 20, 18, 4, 6, 8, 1, 0]

🔧Step 0. Initial state — arr is empty, len is 0. It means that there are no numbers in arr

step 0 result

🔧Step 1. Current number:10. Let’s see where we should place 10 in arr.
Since there’s no number in arr, we just place 10 into arr. We can expand arr, hence len is increased by 1.

step 1 result

🔧Step 2. Current number: 9. Let’s see where we should place 9 in arr.
We found that the position we can place 9 is overlapped with the position we place 10, hence 10 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 2 result

🔧Step 3. Current number: 2. Let’s see where we should place 2 in arr.
We found that the position we can place 2 is overlapped with the position we place 9, hence 9 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 3 result

🔧Step 4. Current number: 5. Let’s see where we should place 5 in arr.
We found that 5 is greater than all the numbers in arr. We will place 5 right after the last number in arr. We can expand arr in this round, len is increased by 1.

step 4 result

🔧Step 5. Current number: 3. Let’s see where we should place 3 in arr.
We found that the position we can place 3 is overlapped with the position we place 5, hence 5 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 5 result

🔧Step 6. Current number: 7. Let’s see where we should place 7 in arr.
We found that 7 is greater than all the numbers in arr. We will place 7 right after the last number in arr. We can expand arr in this round, len is increased by 1.

step 6 result

🔧Step 7. Current number: 20. Let’s see where we should place 20 in arr.
We found that 20 is greater than all the numbers in arr. We will place 20 right after the last number in arr. We can expand arr in this round, len is increased by 1.

step 7 result

🔧Step 8. Current number: 18. Let’s see where we should place 18 in arr.
We found that the position we can place 18 is overlapped with the position we place 20, hence 20 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 8 result

🔧Step 9. Current number: 4. Let’s see where we should place 4 in arr.
We found that the position we can place 4 is overlapped with the position we place 7, hence 7 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 9 result

🔧Step 10. Current number: 6. Let’s see where we should place 6 in arr.
We found that the position we can place 6 is overlapped with the position we place 18, hence 18 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 10 result

🔧Step 11. Current number: 8. Let’s see where we should place 8 in arr.
We found that 8 is greater than all the numbers in arr. We will place 8 right after the last number in arr. We can expand arr in this round, len is increased by 1.

step 11 result

🔧Step 12. Current number: 1. Let’s see where we should place 1 in arr.
We found that the position we can place 1 is overlapped with the position we place 2, hence 2 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 12 result

🔧Step 13. Current number: 0. Let’s see where we should place 0 in arr.
We found that the position we can place 0 is overlapped with the position we place 1, hence 1 is replaced by the current number. We can not expand arr in this round, len remains the same.

step 13 result

👷Done! The length of the longest increasing subsequence is 5 which we found in step11.

Below is the 2ms code that beats 98% -

public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        int len = 0; 
        for(int cur: nums)
        {
            int indx = binarySearch(arr,cur,len);
            arr[indx] = cur;
            if(indx == len)
                len++;
        }
        return len;
    }
    public int binarySearch(int[] arr,int target,int n){
        if(n==0)
            return 0;
        int s = 0, e = n-1;
        while(s<e)
        {
            int mid = s + (e-s)/2;
            if(target == arr[mid])
                return mid;
            if(target > arr[mid])
                s = mid+1;
            else
                e = mid-1;
        }
        if(target > arr[s]) //we can expand arr
            return s+1; 
        else
            return s; //target replace original arr[s]
    }