Skip to content

1035. Uncrossed Lines

On LeetCode ->

Problem

Given two integer arrays, match equal values across them while preserving their relative order; each index may be used once. Return the maximum number of matches.

nums1 = [1, 4, 2], nums2 = [1, 2, 4]
matches = [(0, 0), (2, 1)]
output = 2

Key trick

Uncrossed lines must connect indices in increasing order in both arrays, so the answer is exactly their longest common subsequence length.

Trap

  • Greedily matching the earliest equal values can prevent a better later matching.
  • In the 1D DP optimization, the diagonal value must be saved before dp[j] is overwritten.
  • Updating dp in the wrong order mixes values from the current and previous rows.

Why is it interesting?

A geometric non-crossing constraint becomes an order constraint, reducing the problem to classic longest common subsequence DP with optional space optimization.

Python solution

class Solution:
    def maxUncrossedLines(self, nums1: list[int], nums2: list[int]) -> int:
        # Use the shorter array for the DP row.
        if len(nums1) < len(nums2):
            nums1, nums2 = nums2, nums1

        dp = [0] * (len(nums2) + 1)

        for x in nums1:
            # Value of dp[j - 1] from the previous row.
            prev_diag = 0

            for j, y in enumerate(nums2, 1):
                # Save dp[j] from the previous row before overwriting it.
                above = dp[j]

                if x == y:
                    dp[j] = prev_diag + 1
                else:
                    dp[j] = max(dp[j], dp[j - 1])

                prev_diag = above

        return dp[-1]

Time complexity: \(O(mn)\)

Space complexity: \(O(\min(m,n))\)

Comment on my solution

Your 2D DP solution is correct, clear, and interview-ready, with \(O(mn)\) time and \(O(mn)\) space.

The 1D approach is also correct in principle, but this line stores an input value rather than the previous DP value:

above = n2

It must be:

above = dp[j]

prev_diag represents the old dp[j - 1] from the previous row. Assigning n2 corrupts that state and can produce impossible counts such as 3 for [1, 4, 2] and [1, 2, 4].

# Ideas
# - It seems the construction description connect numbers of the longest
#   common subsequence between both arrays
# - So we can use 2D DP on prefixes dp[i][j] max common subsequence between
#   nums1[:i] and nums[:j].  we extend dp[i][j] from dp[i-1][j-1] when
#   nums1[i] == nums[j]
# - as it depends only on the previous line it can be extented to 1D DP
# - [2 ,5,1,2,5]
# - [10,5,2,1,5,2]

# WORKS
class Solution:
    def maxUncrossedLines(self, nums1: list[int], nums2: list[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return dp[m][n]

Solution().maxUncrossedLines([2 ,5,1,2,5], [10,5,2,1,5,2])

# Wrong Answer: 19/74 testcases passed
# [1,4,2], [1,2,4]
# Output: 3
# Expected: 2
class Solution:
    def maxUncrossedLines(self, nums1: list[int], nums2: list[int]) -> int:
        if len(nums1) < len(nums2):
            nums1, nums2 = nums2, nums1
        dp = [0] * (len(nums2) + 1)
        for n1 in nums1:
            prev_diag = 0
            for j, n2 in enumerate(nums2, 1):
                above = n2
                if n1 == n2:
                    dp[j] = prev_diag + 1
                else:
                    dp[j] = max(dp[j], dp[j-1])
                prev_diag = above
        return dp[-1]