Uncrossed Lines

How it works

We can further optimize by using a single array and a variable to track the diagonal value from the previous iteration. This requires careful handling to avoid overwriting values we still need.

Steps

1. If nums2 is longer than nums1, swap them so we iterate over the longer array in the outer loop. This minimizes space usage.
2. Initialize a 1D array dp of size m+1 with zeros.
3. For each element in nums1:
   • Track prev to store the diagonal value before it gets overwritten.
   • For each element j in nums2:
     • Save dp[j+1] as temp before updating.
     • If elements match, dp[j+1] = 1 + prev.
     • Otherwise, dp[j+1] = max(dp[j+1], dp[j]).
     • Update prev = temp for the next iteration.
4. Return dp[m].

Complexity

• Time complexity: O(n * m)
• Space complexity: O(min(n, m))

Where n and m are the sizes of the arrays nums1 and nums2 respectively.

Things to watch for

Not Recognizing This as LCS

Many struggle to identify that this problem is equivalent to finding the Longest Common Subsequence (LCS). The "uncrossed lines" constraint naturally maps to the subsequence property where relative order must be preserved. Failing to make this connection leads to overcomplicated solutions.

Off-by-One Errors in DP Table

When implementing the bottom-up DP solution, a common mistake is using incorrect indices. The DP table is typically sized (n+1) x (m+1) to handle base cases, but accessing nums1[i] vs dp[i+1] can be confusing. Ensure consistency between array indices and DP table indices.

Incorrect Pointer Movement in Space-Optimized DP

When using space-optimized DP with a single array, forgetting to track the previous diagonal value before overwriting leads to incorrect results. The prev variable must capture dp[j] before it gets updated, as this value is needed for the next iteration's diagonal lookup.

from typing import List

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        if m > n:
            n, m = m, n
            nums1, nums2 = nums2, nums1

        dp = [0] * (m + 1)

        for i in range(n):
            prev = 0
            for j in range(m):
                temp = dp[j + 1]
                if nums1[i] == nums2[j]:
                    dp[j + 1] = 1 + prev
                else:
                    dp[j + 1] = max(dp[j + 1], dp[j])
                prev = temp

        return dp[m]

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        if (m > n) {
            swap(nums1, nums2);
            swap(n, m);
        }

        vector<int> dp(m + 1, 0);

        for (int i = 0; i < n; i++) {
            int prev = 0;
            for (int j = 0; j < m; j++) {
                int temp = dp[j + 1];
                if (nums1[i] == nums2[j]) {
                    dp[j + 1] = 1 + prev;
                } else {
                    dp[j + 1] = max(dp[j + 1], dp[j]);
                }
                prev = temp;
            }
        }

        return dp[m];
    }
};