Teaching Kids Programming – Find Max Number of Uncrossed Lines (Longest Common Subsequence) via Space Optimisation Bottom Up Dynamic Programming Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Uncrossed Lines

Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

Constraints:
1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

Find Max Number of Uncrossed Lines (Longest Common Subsequence) via Space Optimisation Bottom Up Dynamic Programming Algorithm

We know the Bottom Up Dynamic Programming (DP) Algorithm to Compute the Longest Common Subsequence (LCS) as we talked about here: Teaching Kids Programming – Find Max Number of Uncrossed Lines (Longest Common Subsequence) via Bottom Up Dynamic Programming Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
 
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):
        n1 = len(nums1)
        n2 = len(nums2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]

        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

The dp[i][j] is only dependent on dp[i-1][j] and dp[i][j-1] or dp[i-1][j-1], thus, we don’t need to store entire 2D DP Matrix, instead, we can use only two single arrays, one for the previous row e.g. dp[i-1], and one ofr the current row dp[i]. Then, we can optimise the DP solution to O(N) space where N is the less of N1 and N2 (the lengths for two arrays). The time complexity is O(N1*N2).

Each iteration, we set the current row to previous row via Deep Copy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
 
        # Space complexity O(n2) thus swap if n1 is smaller
        if n1 < n2:
            return self.maxUncrossedLines(nums2, nums1)
 
        # dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        # only allocate a row (n2 size)
        dp = [0] * (n2 + 1)
 
        # deep copy
        dp_prev = copy.deepcopy(dp)
 
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
 
                if nums1[i - 1] == nums2[j - 1]:
                    # dp[i][j] = dp[i - 1][j - 1] + 1
                    dp[j] = dp_prev[j - 1] + 1
                else:
                    # dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                    dp[j] = max(dp_prev[j], dp[j - 1])
 
            dp_prev = dp[:]
 
        return dp[-1]

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2) -> int:
        n1 = len(nums1)
        n2 = len(nums2)

        # Space complexity O(n2) thus swap if n1 is smaller
        if n1 < n2:
            return self.maxUncrossedLines(nums2, nums1)

        # dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        # only allocate a row (n2 size)
        dp = [0] * (n2 + 1)

        # deep copy
        dp_prev = copy.deepcopy(dp)

        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):

                if nums1[i - 1] == nums2[j - 1]:
                    # dp[i][j] = dp[i - 1][j - 1] + 1
                    dp[j] = dp_prev[j - 1] + 1
                else:
                    # dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                    dp[j] = max(dp_prev[j], dp[j - 1])

            dp_prev = dp[:]

        return dp[-1]

Find Max Number of Uncrossed Lines (Longest Common Subsequence)

Here are some problems/posts on solving the Longest Common Subsequence (LCS) via the DP (Dynamic Programming) algorithms:

• Teaching Kids Programming – Find Max Number of Uncrossed Lines (Longest Common Subsequence) via Space Optimisation Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming – Find Max Number of Uncrossed Lines (Longest Common Subsequenc) via Bottom Up Dynamic Programming Algorithm
• Dynamic Algorithm to Compute the Longest Common Subsequence
• Teaching Kids Programming – Find Max Number of Uncrossed Lines via Top Down Dynamic Programming Algorithm (Recursion + Memoization)

–EOF (The Ultimate Computing & Technology Blog) —