Domain 2MediumMEDIUM

Uncrossed Lines

Find the maximum number of uncrossed lines between two arrays by mapping the problem to finding the Longest Common Subsequence (LCS) using Dynamic Programming.

Domain: medium•Updated: 2026-09-06
#dynamic programming#longest common subsequence#O(n*m)#space optimization

Problem Breakdown

We are given two integer lists A and B. We need to draw non-intersecting lines connecting equal values (A[i]==B[j]A[i] == B[j]). Each number can be used at most once. The goal is to maximize the count of these valid connections.

  • Inputs: Two arrays, A and B, 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 A[i]A[i] with B[j]B[j], any subsequent connection must use indices strictly greater than both ii and jj. 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 (i,j)(i, j) where A[i]==B[j]A[i] == B[j] 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 A[i]A[i] and B[j]B[j], any future matches must occur at indices strictly greater than ii and jj. 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

  1. Define a DP table dp[i][j] where ii ranges from 00 to len(A)\text{len}(A) and jj ranges from 00 to len(B)\text{len}(B).
  2. Initialize the first row and column with zeros, representing that if one array is empty (prefix length 0), we can draw zero lines.
  3. Iterate through each element of A (ii from 11 to len(A)\text{len}(A)) and B (jj from 11 to len(B)\text{len}(B)).
  4. 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]).
  5. The value at dp[len(A)][len(B)] will be our answer.

Complexity Analysis

  • Time Complexity: O(N×M)O(N \times M), where NN and MM 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: O(N×M)O(N \times M) for the 2D array used to store intermediate results. Given constraints (N,M≤500N, M \leq 500), this fits comfortably within memory limits (approx. 1MB). Note: This can be optimized to O(min⁡(N,M))O(\min(N, M)) 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 A[i]==B[j]A[i] == B[j] 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, else 0.