Problem Description

You have two integer arrays nums1 and nums2 written on two separate horizontal lines in their given order.

Your task is to draw straight lines connecting numbers from nums1 to nums2 following these rules:

• You can only connect nums1[i] to nums2[j] if they have the same value (nums1[i] == nums2[j])
• The connecting lines cannot cross each other
• Each number can only be part of one connection (lines cannot share endpoints)

The goal is to find the maximum number of such non-crossing lines you can draw.

For example, if nums1 = [1, 4, 2] and nums2 = [1, 2, 4], you could connect:

• nums1[0] (value 1) to nums2[0] (value 1)
• nums1[2] (value 2) to nums2[1] (value 2)

This gives you 2 lines maximum. You cannot also connect nums1[1] (value 4) to nums2[2] (value 4) because that line would cross the line connecting the 2s.

The problem is essentially finding the longest common subsequence between the two arrays while maintaining the relative order, which ensures the lines don't cross.

Intuition

The key insight is recognizing that lines won't cross if we maintain the relative order of connections. When we connect nums1[i] to nums2[j] and nums1[k] to nums2[l], the lines won't cross if and only if:

• When i < k, we must have j < l
• When i > k, we must have j > l

This means we're essentially looking for matching elements that preserve their relative positions in both arrays - which is exactly the Longest Common Subsequence (LCS) problem in disguise.

Think about it this way: as we scan through both arrays from left to right, whenever we find matching values, we can either:

1. Draw a line between them (if they equal)
2. Skip the current element in nums1 and look for matches later in nums2
3. Skip the current element in nums2 and look for matches later in nums1

This naturally leads to a dynamic programming approach where we build up the solution by considering prefixes of both arrays. For each position (i, j), we ask: "What's the maximum number of non-crossing lines we can draw using the first i elements of nums1 and the first j elements of nums2?"

The beauty is that when nums1[i-1] == nums2[j-1], we can safely add this connection to whatever optimal solution we had for the smaller subproblem (i-1, j-1), knowing it won't cross any previous lines. When they don't match, we take the better option between excluding the current element from either array.

This builds up our solution incrementally, ensuring we always maintain the maximum possible connections without any crossings.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using a 2D dynamic programming table f[i][j] where each cell represents the maximum number of non-crossing lines we can draw between the first i elements of nums1 and the first j elements of nums2.

Initialization:

• Create a 2D table f with dimensions (m+1) × (n+1) where m = len(nums1) and n = len(nums2)
• Initialize all values to 0, since with 0 elements from either array, we can draw 0 lines

State Transition: For each position (i, j) where 1 ≤ i ≤ m and 1 ≤ j ≤ n:

1. When elements match (nums1[i-1] == nums2[j-1]):

   • We can draw a line connecting these matching elements
   • This adds 1 to the optimal solution of the subproblem without these elements
   • Formula: f[i][j] = f[i-1][j-1] + 1

2. When elements don't match (nums1[i-1] != nums2[j-1]):

   • We can't connect these elements
   • We take the maximum of two options:
     • Exclude element from nums1: use solution from f[i-1][j]
     • Exclude element from nums2: use solution from f[i][j-1]
   • Formula: f[i][j] = max(f[i-1][j], f[i][j-1])

Building the Solution: The algorithm iterates through all pairs of indices using nested loops:

• Outer loop: i from 1 to m (considering each element in nums1)
• Inner loop: j from 1 to n (considering each element in nums2)

Note that we use 1-based indexing for the DP table while the arrays use 0-based indexing, hence we access nums1[i-1] and nums2[j-1] when filling f[i][j].

Final Answer: The value at f[m][n] gives us the maximum number of non-crossing lines between all elements of both arrays.

The time complexity is O(m × n) for filling the DP table, and space complexity is also O(m × n) for storing the table.

Example Walkthrough

Let's walk through a concrete example with nums1 = [2, 5, 1, 2, 5] and nums2 = [10, 5, 2, 1, 5, 2].

We'll build a DP table f[i][j] where f[i][j] represents the maximum number of non-crossing lines we can draw using the first i elements of nums1 and first j elements of nums2.

Initial Setup:

• Create a table with dimensions 6×7 (including row/column for empty arrays)
• Initialize all values to 0

Step-by-step filling:

Starting state (all zeros):

    ""  10  5  2  1  5  2
""   0   0  0  0  0  0  0
2    0   ?  ?  ?  ?  ?  ?
5    0   ?  ?  ?  ?  ?  ?
1    0   ?  ?  ?  ?  ?  ?
2    0   ?  ?  ?  ?  ?  ?
5    0   ?  ?  ?  ?  ?  ?

Row 1 (nums1[0] = 2):

• Compare 2 with each element in nums2
• 2 ≠ 10: f[1][1] = max(f[0][1], f[1][0]) = 0
• 2 ≠ 5: f[1][2] = max(f[0][2], f[1][1]) = 0
• 2 = 2: f[1][3] = f[0][2] + 1 = 1 ✓ (Found match!)
• 2 ≠ 1: f[1][4] = max(f[0][4], f[1][3]) = 1
• 2 ≠ 5: f[1][5] = max(f[0][5], f[1][4]) = 1
• 2 = 2: f[1][6] = f[0][5] + 1 = 1

Row 2 (nums1[1] = 5):

• 5 ≠ 10: f[2][1] = max(f[1][1], f[2][0]) = 0
• 5 = 5: f[2][2] = f[1][1] + 1 = 1 ✓
• 5 ≠ 2: f[2][3] = max(f[1][3], f[2][2]) = 1
• 5 ≠ 1: f[2][4] = max(f[1][4], f[2][3]) = 1
• 5 = 5: f[2][5] = f[1][4] + 1 = 2 ✓
• 5 ≠ 2: f[2][6] = max(f[1][6], f[2][5]) = 2

Row 3 (nums1[2] = 1):

• 1 ≠ 10: f[3][1] = 0
• 1 ≠ 5: f[3][2] = 1
• 1 ≠ 2: f[3][3] = 1
• 1 = 1: f[3][4] = f[2][3] + 1 = 2 ✓
• 1 ≠ 5: f[3][5] = max(f[2][5], f[3][4]) = 2
• 1 ≠ 2: f[3][6] = 2

Row 4 (nums1[3] = 2):

• Following similar logic, when we reach position [4][3] where both values are 2:
• f[4][3] = f[3][2] + 1 = 2
• When we reach [4][6] where both are 2:
• f[4][6] = f[3][5] + 1 = 3

Row 5 (nums1[4] = 5):

• The second 5 in nums1 can match with either 5 in nums2
• Best result comes from matching with the second 5:
• f[5][5] = f[4][4] + 1 = 3
• Final cell: f[5][6] = max(f[4][6], f[5][5]) = 3

Final DP Table:

    ""  10  5  2  1  5  2
""   0   0  0  0  0  0  0
2    0   0  0  1  1  1  1
5    0   0  1  1  1  2  2
1    0   0  1  1  2  2  2
2    0   0  1  2  2  2  3
5    0   0  1  2  2  3  3

Answer: f[5][6] = 3

The three non-crossing lines connect:

1. nums1[1] (5) → nums2[1] (5)
2. nums1[2] (1) → nums2[3] (1)
3. nums1[3] (2) → nums2[5] (2)

These connections maintain order (indices increase in both arrays), ensuring no lines cross.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of nums1 and n is the length of nums2. This is because the algorithm uses two nested loops: the outer loop iterates through all elements of nums1 (m iterations), and the inner loop iterates through all elements of nums2 (n iterations). Each cell in the DP table f[i][j] is computed exactly once with constant time operations.

The space complexity is O(m × n). The algorithm creates a 2D DP table f with dimensions (m + 1) × (n + 1) to store the intermediate results. This table requires O((m + 1) × (n + 1)) = O(m × n) space to store all the computed values for the dynamic programming solution.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion Between DP Table and Arrays

The Pitfall: One of the most common mistakes is mixing up the indexing between the DP table (1-based) and the original arrays (0-based). Developers often write:

• if nums1[i] == nums2[j]: instead of if nums1[i-1] == nums2[j-1]:
• dp[i][j] = dp[i-1][j-1] + 1 when i and j are array indices (0-based)

This leads to index out of bounds errors or incorrect results.

Solution: Always remember that dp[i][j] represents the solution for the first i elements of nums1 and first j elements of nums2. When accessing array elements inside the loop where i ranges from 1 to m, use nums1[i-1] and nums2[j-1].

2. Incorrect DP Table Initialization

The Pitfall: Creating the DP table with wrong dimensions like:

• dp = [[0] * n for _ in range(m)] (missing the +1)
• dp = [[0] * (m + 1) for _ in range(n + 1)] (swapped dimensions)

Solution: Always create the table as dp = [[0] * (n + 1) for _ in range(m + 1)] where the outer list has m+1 rows and each row has n+1 columns. The extra row and column handle the base case of 0 elements.

3. Space Optimization Attempt Gone Wrong

The Pitfall: Trying to optimize space by using a 1D array but not properly handling the dependency on dp[i-1][j-1]:

# Incorrect optimization
dp = [0] * (n + 1)
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if nums1[i-1] == nums2[j-1]:
            dp[j] = dp[j-1] + 1  # Wrong! This uses the current row's j-1

Solution: If optimizing for space, you need to carefully preserve the previous diagonal value:

dp = [0] * (n + 1)
for i in range(1, m + 1):
    prev = 0  # Store dp[i-1][j-1]
    for j in range(1, n + 1):
        temp = dp[j]  # Save current value before updating
        if nums1[i-1] == nums2[j-1]:
            dp[j] = prev + 1
        else:
            dp[j] = max(dp[j], dp[j-1])
        prev = temp  # Update prev for next iteration

4. Misunderstanding the Problem as Maximum Matching

The Pitfall: Thinking the problem asks for the maximum number of connections regardless of crossing, leading to solutions that count all matching pairs:

# Wrong approach
count = 0
for num in nums1:
    if num in nums2:
        count += 1

Solution: Remember that lines cannot cross. The problem is essentially finding the Longest Common Subsequence (LCS), where the order matters. The DP approach ensures we only count non-crossing connections by maintaining the relative order of elements.