Problem Breakdown
We are given two integer lists A and B. We need to draw non-intersecting lines connecting equal values (). Each number can be used at most once. The goal is to maximize the count of these valid connections.
- Inputs: Two arrays,
AandB, containing integers up to 2000 with lengths between 1 and 500. - Output: An integer representing the maximum number of uncrossed lines.
- Implicit Constraints:
- If we connect with , any subsequent connection must use indices strictly greater than both and . This preserves relative order in both arrays simultaneously (subsequence property).
- Each element can participate in at most one line.
Intuition
The problem asks for the maximum number of non-crossing connections between equal elements while maintaining their original relative orders.
A brute-force approach would try to pick every possible pair where and then recursively check if adding this line prevents future lines from crossing or using the same indices. This leads to an exponential time complexity because of overlapping subproblems (e.g., deciding whether to use index k depends on previous choices).
The key insight is recognizing that “uncrossed lines” implies preserving relative order in both arrays. If we select a match at and , any future matches must occur at indices strictly greater than and . This structural constraint defines the Longest Common Subsequence (LCS) problem: finding the longest sequence of elements that appear in A and B in the same relative order.
Therefore, we can solve this using Dynamic Programming to find the LCS length between A and B.
Approach
- Define a DP table
dp[i][j]where ranges from to and ranges from to . - Initialize the first row and column with zeros, representing that if one array is empty (prefix length 0), we can draw zero lines.
- Iterate through each element of
A( from to ) andB( from to ). - Transition Logic:
- If the current elements match (
A[i-1] == B[j-1]), we extend a previous valid line:dp[i][j] = dp[i-1][j-1] + 1. - If they do not match, we cannot connect these specific indices. We take the best result from either skipping an element in A or skipping an element in B:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- If the current elements match (
- The value at
dp[len(A)][len(B)]will be our answer.
Complexity Analysis
- Time Complexity: , where and are the lengths of arrays A and B respectively. We visit every cell in the DP table exactly once performing constant work per cell.
- Space Complexity: for the 2D array used to store intermediate results. Given constraints (), this fits comfortably within memory limits (approx. 1MB). Note: This can be optimized to space by only keeping two rows of history, but the full matrix is clearer for explanation and sufficient here.
Solution
from typing import List
class Solution:
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
# Initialize DP table with dimensions (len(A) + 1) x (len(B) + 1).
# dp[i][j] stores the maximum lines for prefixes A[:i] and B[:j].
n, m = len(A), len(B)
dp = [[0] * (m + 1) for _ in range(n + 1)]
# Iterate through both arrays.
# We use i-1 to access actual element of A because row index is prefix length.
for i in range(1, n + 1):
for j in range(1, m + 1):
if A[i - 1] == B[j - 1]:
# If elements match, extend the solution from diagonal (previous prefixes)
dp[i][j] = dp[i - 1][j - 1] + 1
else:
# If no match, take max of skipping current element in A or B.
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
Edge Cases Handled
- No Matches: The DP table remains initialized to zeros, correctly returning
0. - Duplicates in A or B: Since we iterate by index and check values at each step, duplicate values are treated as distinct items based on their position. If matches a previous value used elsewhere, the logic naturally handles it because indices must increase (LCS property).
- Single Element Arrays: The loops handle length 1 correctly; if they match
dp[1][1]=1, else0.