Uncrossed Lines

Problem Description

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. Return the maximum number of connecting lines we can draw in this way.

Key Insights

• The problem can be reduced to finding the Longest Common Subsequence (LCS) between the two arrays.
• Each line corresponds to a match between elements in nums1 and nums2.
• We can use dynamic programming to efficiently solve the problem by building a 2D table to store the lengths of common subsequences.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2, respectively.
Space Complexity: O(m * n) for the DP table.

Solution

We can use a dynamic programming approach to solve the problem. We will create a 2D array dp where dp[i][j] represents the maximum number of uncrossed lines that can be formed using the first i elements of nums1 and the first j elements of nums2. The approach involves iterating through both arrays and filling in the dp table based on whether the elements match or not.

1. Initialize a 2D array dp with dimensions (len(nums1) + 1) x (len(nums2) + 1) filled with zeros.
2. Iterate through each element of both arrays.
3. If elements match, increment the value from the previous diagonal cell dp[i-1][j-1] by 1.
4. If they do not match, take the maximum from the left or above cells dp[i-1][j] or dp[i][j-1].
5. The final answer will be found at dp[len(nums1)][len(nums2)].

Code Solutions