Teaching Kids Programming – Find Max Number of Uncrossed Lines (Longest Common Subsequence) via Top Down Dynamic Programming Algorithm (Recursion + Memoization)

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 via Top Down Dynamic Programming Algorithm (Recursion + Memoziation)

We can look the two numbers at two ends (either left or right end), if these two numbers are equal, we can greedily connect a line between them (since that they won’t intersect the other lines later), and we can remove these two numbers and look at a smaller sub problem. Otherwise, there are two cases: removing one of them and solve a smaller problem (sub problem).

Without loss of generality, we can look at the process of removing numbers from right to left. Let dp(i, j) be the max number of line segments for nums1[:i+1] and nums2[:j+1]. Then we have the following:

If nums1[i] == nums[j] then
else:

Terminal cases: if i or j crosses the left boundary (i is smaller than zero, or j is smaller than zero).

We can solve this via Dynamic Programming Algorithm – and this can be implemented via Top Down or Bottom Up. We will look at the Top Down Dynamic Programming aka Recursion with Memoziation.

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):

        @cache
        def dp(i, j):
            if i < 0 or j < 0:
                return 0
            if nums1[i] == nums2[j]:
                return 1 + dp(i - 1, j - 1)
            return max(dp(i - 1, j), dp(i, j - 1))

        return dp(len(nums1) - 1, len(nums2) - 1)

If we handle the numbers from left to the right, we have a similar DP approach.

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):

        @cache
        def dp(i, j):
            if i >= len(nums1) or j >= len(nums2):
                return 0
            if nums1[i] == nums2[j]:
                return 1 + dp(i + 1, j + 1)
            return max(dp(i + 1, j), dp(i, j + 1))

        return dp(0, 0)

Both implementations take O(NM) time/space complexity where N and M are the number of elements in two arrays respectively.

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) —