Uncrossed Lines: LCS in Disguise

You are given two integer arrays nums1 and nums2. You can draw lines connecting nums1[i] to nums2[j] whenever nums1[i] == nums2[j], but the lines must not cross each other. Return the maximum number of uncrossed lines you can draw.

This is LeetCode 1035: Uncrossed Lines. At first it looks like a geometry problem, but the constraint that lines cannot cross is the key to unlocking a much simpler formulation.

Why this is the Longest Common Subsequence

Two lines cross when the indices they connect are "out of order." If you connect nums1[i] to nums2[j] and also connect nums1[i'] to nums2[j'], those lines cross exactly when i is before i' but j is after j' (or vice versa). In other words, the lines do not cross if and only if both the selected indices in nums1 and the selected indices in nums2 form increasing sequences.

That is exactly what a common subsequence is. You are picking elements that appear in the same relative order in both arrays. The maximum number of uncrossed lines is therefore the length of the longest common subsequence (LCS) of nums1 and nums2.

If you have already solved Longest Common Subsequence, you can apply the same 2D DP table directly. The only difference is that you are comparing integers instead of characters.

Building the 2D DP table

Define dp[i][j] as the maximum number of uncrossed lines between nums1[0..i-1] and nums2[0..j-1]. The table has (m + 1) rows and (n + 1) columns, where m and n are the lengths of the two arrays.

The recurrence:

1. If nums1[i-1] == nums2[j-1], draw a line between them: dp[i][j] = dp[i-1][j-1] + 1
2. If they are not equal, take the better of skipping one element from either array: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base case: the first row and first column are all 0, because you cannot draw any lines when one array is empty.

Let's trace through nums1 = [1, 4, 2] and nums2 = [1, 2, 4]:

The answer is dp[3][3] = 2. You can draw two uncrossed lines: connect the 1s and connect the 4s.

Python solution

def max_uncrossed_lines(nums1, nums2):
    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]

Time: O(m * n). Every cell in the 2D table gets filled exactly once.

Space: O(m * n). The full table.

Space optimization

Since each row only depends on the previous row, you can reduce space to O(n) by keeping just two rows:

def max_uncrossed_lines(nums1, nums2):
    m, n = len(nums1), len(nums2)
    prev = [0] * (n + 1)

    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr

    return prev[n]

Time: O(m * n). Same as before.

Space: O(n). Only two rows of length n + 1.

Complexity analysis

Where m = length of nums1, n = length of nums2.

Building blocks

This problem is built on two patterns:

1. Longest Common Subsequence (2D DP). The core structure is a 2D table where dp[i][j] compares two sequences. When elements match, you take the diagonal plus one. When they do not match, you take the max of the cell above and the cell to the left. This is the same recurrence used in string LCS problems, and it applies identically to integer arrays.

2. Problem reduction. The real skill here is recognizing that "uncrossed lines" is just LCS in a visual wrapper. Many medium-difficulty problems are known patterns wearing a costume. If you can strip away the story and identify the underlying structure, the solution writes itself.

Edge cases to watch for

• One or both arrays empty: return 0. The base case handles this naturally.
• Identical arrays: every element matches on the diagonal. The answer equals the length of the arrays.
• No common elements: no lines can be drawn. dp[m][n] = 0.
• All elements the same: e.g., nums1 = [3, 3, 3] and nums2 = [3, 3]. The answer is min(m, n) because every element matches, but you can only draw as many lines as the shorter array allows.
• Duplicate values: the DP handles duplicates correctly. Each cell considers only whether the current pair of elements matches, not how many times a value appears.

From understanding to recall

You have seen that uncrossed lines is the Longest Common Subsequence wearing a different outfit. The 2D DP table is identical, and the recurrence is the same match-or-skip logic. But recognizing this equivalence under interview pressure is the hard part.

The next time you see a problem about matching elements across two sequences without crossing, you need the LCS pattern to fire immediately. That recognition does not come from reading about it once. It comes from practicing both problems until the connection is automatic.

The LCS pattern is one of roughly 60 reusable building blocks in the CodeBricks system. You drill each block individually with spaced repetition until writing the solution from scratch is second nature. Uncrossed Lines is a perfect example of why drilling the core patterns pays off: once you own LCS, you get this problem for free.

Related posts

• Longest Common Subsequence - The exact same problem in string form
• Edit Distance - Another 2D DP comparing two sequences
• Distinct Subsequences - Counting subsequence matches between sequences