Problem Description

You are given two integer arrays, A and B. You want to draw lines connecting elements from A to elements from B such that:

• Each line connects A[i] to B[j] if and only if A[i] == B[j].
• No two lines cross (lines are not allowed to intersect).
• Each element in A and B can be connected at most once (no reusing elements).

The task is to return the maximum number of lines you can draw under these constraints.

This problem is similar to finding the length of the Longest Common Subsequence (LCS) between A and B, since the lines cannot cross and elements cannot be reused.

Thought Process

At first glance, one might try every possible way to connect equal elements between A and B without crossing lines. However, this brute-force approach is highly inefficient because the number of possible combinations grows rapidly with the length of the arrays.

To optimize, we recognize that the problem is equivalent to finding the Longest Common Subsequence (LCS) between the two arrays. In LCS, we find the longest sequence that appears in both arrays in the same order (but not necessarily consecutively), and this naturally avoids crossings and reusing elements.

By mapping the problem to LCS, we can use dynamic programming to efficiently compute the answer.

Solution Approach

We solve the problem using dynamic programming (DP), specifically the classic LCS technique. Here's how:

1. Define the DP Table:
   • Let dp[i][j] represent the maximum number of non-crossing lines (matches) we can draw between the first i elements of A and the first j elements of B.
2. Base Case:
   • If either i == 0 or j == 0, there are no elements to match, so dp[0][j] = 0 and dp[i][0] = 0.
3. Recurrence Relation:
   • If A[i-1] == B[j-1], we can draw a line connecting them: dp[i][j] = dp[i-1][j-1] + 1.
   • Otherwise, we skip one element from either A or B: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
4. Final Answer:
   • The value at dp[len(A)][len(B)] gives the maximum number of uncrossed lines.

We use a 2D array for the DP table, which is filled in row by row. This approach ensures that we consider all possible prefixes of A and B and always make the optimal choice at each step.

Example Walkthrough

Let's consider the example: A = [1,4,2], B = [1,2,4].

1. Initialization:
   • Create a dp table of size 4 x 4 (since both arrays have length 3, add 1 for zero-based).
2. Filling the Table:
   • For i=1, j=1: A[0]=1, B[0]=1 (match), so dp[1][1]=dp[0][0]+1=1.
   • For i=1, j=2: A[0]=1, B[1]=2 (no match), so dp[1][2]=max(dp[0][2], dp[1][1])=1.
   • Continue filling the table row by row, always applying the recurrence.
   • Eventually, dp[3][3]=2, meaning the maximum number of uncrossed lines is 2.
3. Result:
   • We can connect A[0]=1 to B[0]=1 and A[2]=2 to B[1]=2 (or A[1]=4 to B[2]=4).

Time and Space Complexity

• Brute-force Approach:
  • Would involve trying all possible subsets of matches, leading to exponential time complexity: O(2^min(m, n)), where m and n are the lengths of A and B.
• Optimized DP Approach:
  • Time Complexity: O(m * n), since we fill a table of size m x n.
  • Space Complexity: O(m * n) for the DP table. This can be reduced to O(min(m, n)) with further optimization (using only two rows).

Summary

The Uncrossed Lines problem is a classic example of recognizing when a seemingly complex matching problem can be solved efficiently using dynamic programming. By mapping the problem to the Longest Common Subsequence, we avoid brute-force enumeration and achieve an elegant, efficient solution. The key insight is that non-crossing, non-reused matches correspond exactly to the LCS property, making this a textbook DP application.

Code Implementation

class Solution:
    def maxUncrossedLines(self, A, B):
        m, n = len(A), len(B)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if A[i-1] == B[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]
    

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A[i-1] == B[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];
    }
};
    

class Solution {
    public int maxUncrossedLines(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}
    

var maxUncrossedLines = function(A, B) {
    let m = A.length, n = B.length;
    let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (A[i-1] === B[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
};