Teaching Kids Programming – Find Max Number of Uncrossed Lines (Longest Common Subsequence) via 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 via Bottom Up Dynamic Programming Algorithm

LeetCode is a popular platform for coding challenges, and one of the interesting problems it offers is problem number 1035 – Uncrossed Lines. This problem requires finding the maximum number of uncrossed lines between two given arrays, nums1 and nums2. In this blog post, we will explore a bottom-up dynamic programming approach to solve this problem in Python.

Understanding the Problem

The problem can be framed as finding the length of the longest common subsequence (LCS) between two arrays. The uncrossed lines represent the elements that can be connected without crossing any other line. By finding the LCS, we can determine the maximum number of uncrossed lines.

Bottom-Up Dynamic Programming Approach

To solve this problem, we can use a bottom-up dynamic programming approach. The code provided uses a two-dimensional array, dp, to store the results of subproblems. The value dp[i][j] represents the length of the LCS between the first i elements of nums1 and the first j elements of nums2.

Let’s break down the code to understand the steps involved:

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

The code initializes the dimensions of the input arrays, nums1 and nums2, as n1 and n2, respectively. It then creates a two-dimensional array, dp, with dimensions (n1 + 1) x (n2 + 1). The “+1” is added to accommodate the base cases where either of the arrays is empty.

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

The nested loops iterate through the elements of nums1 and nums2. For each pair of elements, if they are equal, we increment the LCS length by 1 and store it in dp[i][j]. If they are not equal, we take the maximum LCS length obtained from the previous elements (either by excluding nums1[i] or nums2[j]) and store it in dp[i][j].

        return dp[-1][-1]

Finally, the code returns the value stored in the bottom-right corner of the dp array, which represents the maximum number of uncrossed lines or the length of the LCS.

The bottom-up dynamic programming approach discussed in this blog post provides an efficient solution to LeetCode 1035 – Uncrossed Lines problem. By leveraging the concept of the longest common subsequence, we can determine the maximum number of uncrossed lines between two given arrays. The code provided demonstrates the implementation of this approach in Python. Remember to analyze and understand the problem requirements before applying this technique to other similar scenarios.

The complete Python code (Bottom-up Dynamic Programming) is given as follows:

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 time/space complexity is O(NM) where N and M are the lengths for two arrays respectively. We are computing NM numbers on the grid – and each cell is computed only once.

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