Uncrossed Lines
Problem
Two arrays A and B are written in two rows. Draw a straight line between A[i] and B[j] when A[i] == B[j]. Lines must not cross. Return the maximum number of lines you can draw — this equals the longest common subsequence of A and B.
A = [1, 4, 2], B = [1, 2, 4]2def max_uncrossed_lines(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]function maxUncrossedLines(A, B) {
const m = A.length, n = B.length;
const dp = Array.from({ length: m + 1 }, () => new 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];
}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];
}
}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];
}Explanation
The big insight is that the "non-crossing connecting lines" rule is exactly the same as finding the longest common subsequence (LCS) of the two arrays. A set of lines that never cross corresponds to matched values that appear in the same order in both arrays.
So we build a 2D table dp where dp[i][j] is the most lines we can draw using the first i values of A and the first j values of B.
For each pair of positions we ask one question: do A[i-1] and B[j-1] match? If they do, we connect them and add 1 to the best answer from the smaller problem: dp[i][j] = dp[i-1][j-1] + 1. If they don't, we skip one element from either side and take the better option: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Row 0 and column 0 stay 0 because an empty prefix can connect nothing.
Example: A = [1,4,2], B = [1,2,4]. We can connect both 1s and both 4s (in order), giving 2 non-crossing lines, so dp[3][3] = 2.