300.Longest_Increasing_Subsequence(Medium).md

300. Longest Increasing Subsequence (Medium)

Date and Time: Aug 22, 2024, 17:49 (EST)

Link: https://leetcode.com/problems/longest-increasing-subsequence/

Question:

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

Example 1:

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.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]

Output: 1

Constraints:

• 1 <= nums.length <= 2500

• -10^4 <= nums[i] <= 10^4

Walk-through:

Dynamic Programming: We build a dp = [0] * len(nums), then we start updating dp[i] from backward. For each element, we check its previous elements to see if there exists an element greater than current element, the recurrence relation is dp[i] = max(1, 1 + dp[j]) where dp[j] is the previous element greater than current element. Otherwise, we just store dp[i] = 1 for current element.

Binary Search: We repeatly add elements into res, so we can have strictly increasing subsequence.

1. If element n > res[-1], we can add n into res, because we can form strictly increasing subsequence.

2. If n < res[-1], we use binary search to find place it in res. Because the smaller element won't hurt building the longest increasing subsequence.

3. Finally, return the length of res.

Python DP:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        res = 0
        for i in range(len(nums)-1, -1, -1):
            tmp = 1
            for j in range(i+1, len(nums)):
                if nums[i] < nums[j]:
                    tmp = max(tmp, 1 + dp[j])
            dp[i] = tmp
            res = max(res, tmp)
        return res

Time Complexity: $O(n^2)$, loop over n and each element we check previous elements.
Space Complexity: $O(n)$

Python Binary Search:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = [nums[0]]
        def bs(res, n):
            l, r = 0, len(res) - 1
            while l <= r:
                m = (l + r) // 2
                if res[m] == n:
                    return m
                elif res[m] < n:
                    l += 1
                else:
                    r -= 1
            return l

        for n in nums:
            if res[-1] < n:
                res.append(n)
            else:
                index = bs(res, n)
                res[index] = n
        return len(res)

Time Complexity: $O(nlog\ n)$
Space Complexity: $O(n)$