Challenge

You are given an integer array called nums, your task is to return the longest increasing subsequence.

E.g [0,1,2,7] is the longest subsequence of the array [0,3,1,6,2,2,7]

Solution 1 - Recursion

class Solution:

    def first_solution(self, nums, index, prev, ct):

        if index > len(nums):
            self.m = max(self.m, ct)
            return
        self.first_solution(nums, index + 1, prev, ct)
        if index < len(nums) and nums[index] > prev:
            self.first_solution(nums, index + 1, nums[index], ct + 1)
        return ct

    def lengthOfLIS(self, nums: List[int]) -> int:
        self.m = 0
        self.first_solution(tuple(nums), 0, float("-inf"), 0)
        return self.m

Time complexity: O(n^2)

Solution 2 - Dynamic Programming

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

Time Complexity: O(n^2)

Solution 3 - Using Patience sort

def lis_using_patience_sort(arr):
    stack = [[]]
    for n in arr:
        i = 0
        while i < len(arr)-1:
            if i < len(stack) and len(stack[i]) == 0:
                stack[i].insert(0, n)
                break
            elif i < len(stack)  and len(stack[i]) > 0 and n <= stack[i][0]:
                stack[i].insert(0, n)
                break
            elif i == len(stack)-1 and len(stack[i]) > 0 and n >= stack[i][0]:
                stack.append([n])
                break
            i += 1
    return len(stack)

Simplified implementation using bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = []

        for num in nums:
            if not res or num > res[-1]:
                res.append(num)
            else:
                idx = bisect.bisect_left(res,num)
                res[idx] = num
        return len(res)

Time Complexity: O(n log n)

Credits: youtube video