LeetCode 1035 - Uncrossed Lines

The problem gives us two integer arrays, nums1 and nums2. We are allowed to draw lines between matching values in the two arrays, but with an important restriction: the lines cannot cross each other. A line can only connect nums1[i] with nums2[j] when the values are equal.

leetcodemediumarraydynamic-programming

LeetCode Problem 1035

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2. We are allowed to draw lines between matching values in the two arrays, but with an important restriction: the lines cannot cross each other.

A line can only connect nums1[i] with nums2[j] when the values are equal. Once a number is used in a connection, it cannot be used again. The goal is to maximize the total number of valid, non-crossing connections.

The key observation is that crossing happens when the relative ordering of chosen elements differs between the two arrays. Suppose we connect:

  • nums1[i] to nums2[j]
  • nums1[k] to nums2[l]

If i < k, then we must also have j < l to avoid intersections. This means the matched elements must appear in the same relative order in both arrays.

This is exactly the definition of the Longest Common Subsequence problem. A subsequence preserves order while allowing skipped elements. Therefore, the maximum number of uncrossed lines is equivalent to finding the length of the longest common subsequence between the two arrays.

The input constraints are important:

  • Each array length is at most 500
  • Values range from 1 to 2000

Since the arrays are relatively small, an O(m * n) dynamic programming solution is practical, where m and n are the lengths of the arrays. However, exponential brute-force solutions would be far too slow.

Several edge cases are worth considering:

  • Arrays with no matching values should return 0
  • Arrays where every value matches should return the full length of the smaller array
  • Duplicate values can create multiple matching possibilities, so greedy matching is unsafe
  • Very small arrays of length 1 must still work correctly
  • Order matters, even if the arrays contain the same numbers

Approaches

Brute Force Approach

A brute-force solution would try every possible way of matching elements between the two arrays while ensuring lines do not cross.

For each element in nums1, we could either:

  • Skip it
  • Match it with some valid occurrence in nums2

This creates a recursive decision tree. At every step, we explore multiple possibilities and keep track of the maximum number of valid connections.

The brute-force approach is correct because it eventually explores every possible valid matching arrangement. However, the number of combinations grows exponentially. With array lengths up to 500, this becomes completely impractical.

The main issue is overlapping subproblems. The same suffix pairs of arrays are recomputed repeatedly.

Optimal Dynamic Programming Approach

The critical insight is that this problem is identical to the Longest Common Subsequence problem.

If two matched pairs cross, then their ordering differs between the arrays. Therefore, any valid set of uncrossed lines must preserve relative order in both arrays. That is exactly what a common subsequence does.

We define:

  • dp[i][j] as the maximum number of uncrossed lines using:

  • first i elements of nums1

  • first j elements of nums2

The transition is:

  • If nums1[i - 1] == nums2[j - 1]

  • we can connect them

  • dp[i][j] = dp[i - 1][j - 1] + 1

  • Otherwise:

  • skip one element from either array

  • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

This avoids recomputation and efficiently builds the answer bottom-up.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Recursively explores all matching possibilities
Optimal O(m * n) O(m * n) Dynamic programming based on Longest Common Subsequence

Algorithm Walkthrough

  1. Create a 2D dynamic programming table called dp.

The table has dimensions (len(nums1) + 1) x (len(nums2) + 1). Extra padding simplifies boundary handling because row 0 and column 0 represent empty prefixes. 2. Interpret dp[i][j].

dp[i][j] stores the maximum number of uncrossed lines that can be formed using:

  • the first i elements of nums1
  • the first j elements of nums2
  1. Iterate through both arrays.

Use nested loops:

  • outer loop over nums1
  • inner loop over nums2

At each pair of positions, decide whether the current elements should be connected. 4. Handle matching values.

If nums1[i - 1] == nums2[j - 1], then these two numbers can form a valid line.

Since adding this line preserves ordering, we extend the best solution from the smaller prefixes:

$dp[i][j] = dp[i-1][j-1] + 1$ 5. Handle non-matching values.

If the numbers differ, we cannot connect them directly.

We instead choose the better of:

  • skipping the current element in nums1
  • skipping the current element in nums2

$dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$ 6. Continue filling the table row by row.

Each cell depends only on previously computed cells, so the table naturally builds toward the final solution. 7. Return the bottom-right value.

dp[len(nums1)][len(nums2)] contains the maximum number of uncrossed lines for the entire arrays.

Why it works

The dynamic programming formulation works because every valid uncrossed matching must preserve relative order. When two elements match, we can safely extend a smaller optimal solution without creating crossings. When they do not match, at least one element must be excluded from the optimal solution. Since the recurrence considers all such possibilities and stores optimal subproblem results, the final answer is guaranteed to be optimal.

Python Solution

from typing import List

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        rows = len(nums1)
        cols = len(nums2)

        dp = [[0] * (cols + 1) for _ in range(rows + 1)]

        for i in range(1, rows + 1):
            for j in range(1, cols + 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[rows][cols]

The implementation begins by determining the sizes of both arrays. We then allocate a 2D dynamic programming table initialized with zeros.

The extra row and column simplify handling empty prefixes. For example, dp[0][j] means one array is empty, so no lines can be drawn.

The nested loops process every pair of positions:

  • If the current values match, we extend the previous diagonal result by one.

  • Otherwise, we inherit the best answer from either:

  • excluding the current element from nums1

  • excluding the current element from nums2

Finally, the bottom-right cell contains the optimal answer for the full arrays.

Go Solution

func maxUncrossedLines(nums1 []int, nums2 []int) int {
	rows := len(nums1)
	cols := len(nums2)

	dp := make([][]int, rows+1)
	for i := range dp {
		dp[i] = make([]int, cols+1)
	}

	for i := 1; i <= rows; i++ {
		for j := 1; j <= cols; j++ {
			if nums1[i-1] == nums2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				if dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}

	return dp[rows][cols]
}

The Go implementation follows the same dynamic programming logic as the Python solution.

Since Go does not provide a built-in 2D array initialization shortcut like Python list comprehensions, we explicitly allocate each row using make.

Go slices naturally handle empty arrays correctly, so no special edge-case handling is required. Integer overflow is not a concern because the maximum possible answer is only 500.

Worked Examples

Example 1

Input:

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

We construct the DP table.

i/j 0 1 2 3
0 0 0 0 0
1 0 1 1 1
2 0 1 1 2
3 0 1 2 2

Step-by-step reasoning:

  • 1 == 1, so dp[1][1] = 1
  • 4 == 4, so dp[2][3] = dp[1][2] + 1 = 2
  • 2 == 2, so dp[3][2] = dp[2][1] + 1 = 2

The final answer is:

dp[3][3] = 2

Example 2

Input:

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

Relevant matches include:

  • 5
  • 1
  • 5

One optimal subsequence is:

[5,1,5]

Final DP result:

3

Key transitions:

nums1 value nums2 value Action Result
5 5 Match Extend subsequence
1 1 Match Extend subsequence
5 5 Match Extend subsequence

Example 3

Input:

nums1 = [1,3,7,1,7,5]
nums2 = [1,9,2,5,1]

Possible uncrossed matches include:

  • 1
  • 5

The best valid ordering gives only two connections.

Final answer:

2

A valid subsequence is:

[1,5]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every pair of indices is processed once
Space O(m * n) The DP table stores results for all subproblems

The algorithm uses a nested loop over both arrays, so the total number of state transitions is proportional to m * n.

The DP table also contains m * n cells. Each cell stores a single integer representing the best result for that subproblem.

Test Cases

from typing import List

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        rows = len(nums1)
        cols = len(nums2)

        dp = [[0] * (cols + 1) for _ in range(rows + 1)]

        for i in range(1, rows + 1):
            for j in range(1, cols + 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[rows][cols]

solution = Solution()

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

assert solution.maxUncrossedLines([1], [1]) == 1  # Single matching element
assert solution.maxUncrossedLines([1], [2]) == 0  # Single non-matching element

assert solution.maxUncrossedLines([1,2,3], [1,2,3]) == 3  # Completely identical arrays
assert solution.maxUncrossedLines([1,2,3], [3,2,1]) == 1  # Reverse ordering

assert solution.maxUncrossedLines([1,1,1], [1,1]) == 2  # Duplicate values
assert solution.maxUncrossedLines([5,6,7], [1,2,3]) == 0  # No common values

assert solution.maxUncrossedLines([2,2,2,2], [2,2,2]) == 3  # Repeated identical values

assert solution.maxUncrossedLines(
    [1,3,5,7,9],
    [1,4,5,8,9]
) == 3  # Multiple matching subsequences
Test Why
[1,4,2] vs [1,2,4] Validates crossing restriction
[2,5,1,2,5] vs [10,5,2,1,5,2] Tests multiple matching paths
[1,3,7,1,7,5] vs [1,9,2,5,1] Tests ordering constraints
[1] vs [1] Smallest matching input
[1] vs [2] Smallest non-matching input
Identical arrays Ensures full matching works
Reverse arrays Demonstrates ordering importance
Duplicate-heavy arrays Tests repeated values
No common values Ensures zero result works
Large repeated values Tests many equivalent choices
Mixed subsequences Validates DP decision-making

Edge Cases

Arrays With No Matching Elements

If the two arrays share no common values, the correct answer is 0. This case can expose bugs where the algorithm incorrectly increments matches or mishandles initialization.

For example:

nums1 = [1,2,3]
nums2 = [4,5,6]

Every DP transition falls into the non-matching branch, so all cells remain 0. The implementation handles this naturally through the recurrence relation.

Arrays With Many Duplicate Values

Duplicate values are dangerous for greedy approaches because matching the first available occurrence is not always optimal.

For example:

nums1 = [1,1,1]
nums2 = [1,1]

The optimal answer is 2, not 1.

The DP solution correctly explores all prefix combinations and chooses the optimal arrangement automatically.

Reverse Ordered Arrays

Arrays containing the same values in reverse order are important because they demonstrate why ordering matters.

Example:

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

Even though all values exist in both arrays, only one uncrossed line can be drawn. Any attempt to connect more would create crossings.

The dynamic programming approach correctly enforces order preservation through its subsequence structure.