We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Uncrossed Lines

Number: 1105

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Google

Problem Description

Given two integer arrays, nums1 and nums2, the task is to draw as many connecting lines between matching numbers as possible. Each connecting line must connect nums1[i] with nums2[j] if they are equal, and lines must not cross. Essentially, you must find the maximum number of matching pairs that preserve the order of both arrays.

Key Insights

  • The problem is equivalent to computing the Longest Common Subsequence (LCS) between nums1 and nums2.
  • Matching numbers can be connected only if they appear in order in both arrays, preventing crossing lines.
  • A dynamic programming approach can be leveraged to build the LCS solution efficiently.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(n * m) for the DP table; this can be optimized to O(min(n, m)) with further improvements.

Solution

To solve the problem, we use dynamic programming to calculate the longest common subsequence (LCS) between the two arrays. We define a 2D DP table where dp[i][j] represents the maximum number of connecting lines that can be drawn considering the first i elements of nums1 and the first j elements of nums2. For each element pair, if the numbers match, we add one to the value from dp[i-1][j-1]. If they do not match, we take the maximum value from either dp[i-1][j] or dp[i][j-1]. This approach systematically builds the answer while ensuring that the order is preserved, thereby avoiding crossing lines.

Code Solutions

# Python solution using dynamic programming for LCS
def max_uncrossed_lines(nums1, nums2):
    n, m = len(nums1), len(nums2)
    # Create a DP table with dimensions (n+1) x (m+1) initialized to 0
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if nums1[i - 1] == nums2[j - 1]:
                # If the elements match, add one to the result from the previous subproblem
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # Otherwise, take the maximum value from the adjacent subproblems
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

# Example usage:
# nums1 = [1,4,2]
# nums2 = [1,2,4]
# print(max_uncrossed_lines(nums1, nums2))  # Output: 2
← Back to All Questions