LeetCode 1035: Uncrossed Lines

Problem Restatement

We are given two integer arrays nums1 and nums2.

We draw lines connecting equal values: nums1[i] to nums2[j] when nums1[i] == nums2[j].

Two lines cannot cross.

We need to return the maximum number of connecting lines we can draw without any crossing.

The official constraints state that 1 <= nums1.length, nums2.length <= 500 and 1 <= nums1[i], nums2[j] <= 2000.

Input and Output

Function shape:

def maxUncrossedLines(nums1: list[int], nums2: list[int]) -> int:
    ...

Examples

Example 1:

nums1 = [1, 4, 2]
nums2 = [1, 2, 4]

We can connect 1-1 and 4-4: two lines, and they don’t cross.

Answer:

2

Example 2:

nums1 = [2, 5, 1, 2, 5]
nums2 = [10, 5, 2, 1, 5, 2]

Maximum uncrossed lines: 3.

Answer:

3

Key Insight

Two connecting lines do not cross if and only if the connected pairs form a subsequence in both arrays.

This is exactly the Longest Common Subsequence (LCS) problem.

Algorithm

Standard LCS DP:

dp[i][j] = LCS length of nums1[:i] and nums2[:j]

Transition:

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

Correctness

Two lines from nums1[i] to nums2[j] and nums1[i'] to nums2[j'] do not cross if and only if i < i' implies j < j'. This is exactly the condition for an increasing subsequence — the LCS.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Let m = len(nums1) and n = len(nums2).

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

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 - 1][j], dp[i][j - 1])

        return dp[m][n]

Testing

def run_tests():
    s = Solution()

    assert s.maxUncrossedLines([1,4,2], [1,2,4]) == 2
    assert s.maxUncrossedLines([2,5,1,2,5], [10,5,2,1,5,2]) == 3
    assert s.maxUncrossedLines([1,3,7,1,7,5], [1,9,2,5,1]) == 2

    print("all tests passed")

run_tests()