Longest Increasing Subsequence (DP)

Pinkerbelle mady by Tinkerbelle © Diane Khambu

Question:

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

Solutions:

Let’s first do the brute force. Since it’s Longest Increasing Subsequence (LIS), we’ll iterate over each element at index i, and check the rest of the elements starting from index i+1 that satisfies the requirement of LIS.

from typing import List
def length_of_LIS(nums: List[int]) -> int:
    max_so_far = 0

    for i in range(len(nums)):
        cur_max = 1
        for j in range(i+1, len(nums)):
            if nums[i] < nums[j]:
                cur_max += 1
        
        max_so_far = max(max_so_far, cur_max)
    return max_so_far


nums = [10, 9,  2, 5, 3, 7, 101, 18]
print(length_of_LIS(nums))  # prints 4

nums1 = [0, 1, 0, 3, 2, 3]
print(length_of_LIS(nums1))  # prints 4

nums2 = [7, 7, 7, 7, 7, 7, 7]
print(length_of_LIS(nums2))  # prints 1

Runtime complexity: O(n^2) where n is the length of the nums array.

Space complexity: O(1).

Since we are targeting to reach the end of the nums array, we can also solve the problem recursively.

from typing import List

def length_of_LIS_helper(nums: List[int], start: int) -> int:
    max_so_far = 0
    for nxt in range(start+1, len(nums)):
        if nums[nxt] > nums[start]:
            max_so_far = max(max_so_far, length_of_LIS_helper(nums, nxt)+1)
        
    return max_so_far

def length_of_LIS(nums: List[int]) -> int:
    # adding `-inf` value to take into account the first element in the array
    nums = [float('-inf')] + nums
    return length_of_LIS_helper(nums, 0)

nums = [10, 9,  2, 5, 3, 7, 101, 18]
print(length_of_LIS(nums))  # prints 4

nums1 = [0, 1, 0, 3, 2, 3]
print(length_of_LIS(nums1))  # prints 4

nums1 = [7, 7, 7, 7, 7, 7, 7]
print(length_of_LIS(nums1))  # prints 1

Here’s a diagram of a recursive call for array [float('-inf'), 10, 9, 2, 5, 3, 7, 101, 18] :

Recursive calls

Once we reach the base case of end of the array, count is increased by 1 and pops off the stack. This process is done for all elements and we return the maximum subsequence value.

Runtime complexity: O(2**n) where n is the length of the array.

Space complexity: O(1)

Since we have repetitive calculation, we can use memoization technique to store calculated values and use this lookup table if the same parameter has been calculated earlier.

from typing import List

def length_of_LIS_helper(nums: List[int], start: int, memo: List[int]) -> int:
    if memo[start]:
        return memo[start]
    
    max_so_far = 0
    for nxt in range(start+1, len(nums)):
        if nums[nxt] > nums[start]:
            max_so_far = max(max_so_far, length_of_LIS_helper(nums, nxt, memo)+1)
    memo[start] = max_so_far
    return max_so_far


def length_of_LIS(nums: List[int]) -> int:
    nums = [float('-inf')] + nums
    memo = [0] * len(nums)
    length_of_LIS_helper(nums, 0, memo)
    return max(memo)


nums = [10, 9,  2, 5, 3, 7, 101, 18]
print(length_of_LIS(nums))  # prints 4

nums1 = [0, 1, 0, 3, 2, 3]
print(length_of_LIS(nums1)) # prints 4

nums2 = [7, 7, 7, 7, 7, 7, 7]
print(length_of_LIS(nums2)) # prints 1 

Now comes the Dynamic Programming (DP) part. It’s similar to brute force, however we store already calculated values and update the lookup table if we find elements that meets LIS requirements.

from typing import List


def length_of_LIS(nums: List[int]) -> int:
    dp = [1] * len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    
    return dp[-1]

nums = [10, 9,  2, 5, 3, 7, 101, 18]
print(length_of_LIS(nums)) # prints 4 

nums1 = [0, 1, 0, 3, 2, 3]
print(length_of_LIS(nums1)) # prints 4

nums1 = [7, 7, 7, 7, 7, 7, 7]
print(length_of_LIS(nums1))  # prints 1

Runtime Complexity: O(n**2) where n is the length of the array.

Space Complexity: O(n) where n is the length of the array.

There it is the DP solution.

Now let’s look at another question with matrix.

Question:

Write an efficient algorithm that searches for a value target in an m*n integer matrix matrix . This matrix has the following propoerties:

• Integers in each row are sorted in ascending from left to right
• Integers in each column are sorted in ascending from top to bottom

t

The straight forward solution is to use binary search for each row. There are many other clever solutions, for now just did the iterative binary search.

from typing import List

def bin_search(row: List[int], target: int) -> bool:
    lo = 0
    hi = len(row)-1

    while lo <= hi:
        mid = lo + (hi-lo)//2
        if row[mid] == target:
            return True
        elif row[mid] < target:
            lo = mid+1
        else:
            hi = mid-1

    return False

def search_matrix(matrix: List[List[int]], target: int) -> bool:
    for row in matrix:
        if bin_search(row, target):
            return True
    return False


matrix = [[1, 4, 7, 11, 15],
          [2, 5, 8, 12, 19],
          [3, 6, 9, 16, 22],
          [10, 13, 14, 17, 24],
          [18, 21, 23, 26, 30]
]

print(search_matrix(matrix, 5))  # prints True

matrix1 = [[1, 4, 7, 11, 15],
           [2, 5, 8, 12, 19],
           [3, 6, 9, 16, 22],
           [10, 13, 14, 17, 24],
           [18, 21, 23, 26, 30]
]
print(search_matrix(matrix1, 20)) # prints False 

Voila! We have reached the end of the post. Congratulations on coming this far in your algorithm journey! 🎈

Until next post, ✨

Inspirations :

• Leetcode

You can support me in Patreon!