300. Longest Increasing Subsequence

Question

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. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

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.

Solution 1: DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1 for i in range(n)] # init for all LIS ending with nums[i]
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

Time Complexity: O(N^2)
Space Complexity: O(N)

Solution 2: Greedy + Binary Search

def bin_srch_left(arr, lft, rht, x):
    while(lft <= rht):
        mid = (lft + rht) // 2
        if arr[mid] > x:
            rht = mid - 1
        elif arr[mid] < x:
            lft = mid + 1
        else:
            return mid # this shouldn't happen because of strictly increase
    return lft

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        listLIS = []
        for v in nums:
            if not listLIS or listLIS[-1] < v:
                listLIS.append(v)
            else:
                idx = bin_srch_left(listLIS, 0, len(listLIS) - 1, v) # OR JUST SIMPLY USE: bisect_left(listLIS, v)
                listLIS[idx] = v
        return len(listLIS)

Time Complexity: O(N*Log(N))
Space Complexity: O(N)

Solution 3: Binary Indexed Tree

Time Complexity: O(N) // O(N*Log(MAX))
Space Complexity: O(1) // O(MAX)

Reference

https://leetcode.com/problems/longest-increasing-subsequence/discuss/2642573/DPpython
https://leetcode.com/problems/longest-increasing-subsequence/discuss/1326308/C%2B%2BPython-DP-Binary-Search-BIT-Solutions-Picture-explain-O(NlogN)
https://yuanchieh.page/posts/2022/2022-05-23-%E7%AE%97%E6%B3%95segment-tree-%E8%88%87-binary-indexed-tree-%E8%A7%A3%E9%A1%8C%E6%95%B4%E7%90%86/

Follow-up:

TODO

Time Complexity: O()
Space Complexity: O()