⚡Flashcard Drill➔
NeetCode #686LC-1035Medium1-D Dynamic Programming
← Back to All Problems

#686 · #1035 · Uncrossed Lines(不相交的线)

📌 Problem Statement & Constraints

You are given two integer arrays nums1 and nums2. Draw connecting lines between equal values, preserving order, so that no two lines cross. Return the maximum number of lines that can be drawn. Constraints: 1 <= nums1.length, nums2.length <= 500, 1 <= nums1[i], nums2[i] <= 2000.

💡 Core Algorithmic Approaches

  1. The order-preserving, non-crossing constraint makes this identical to the longest common subsequence problem.
  2. Let dp[i][j] be the maximum number of lines using the first i elements of nums1 and the first j of nums2.
  3. If nums1[i-1] == nums2[j-1], extend the diagonal: dp[i][j] = dp[i-1][j-1] + 1.
  4. Otherwise drop one element from either side: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): the full DP table.
💾 Space Complexity
O(m * n), reducible to O(n) with a rolling row.

⚠️ Interview Pitfalls & Follow-ups

  • Matching greedily: a locally good match can block a better global alignment, so greedy fails.
  • Drawing lines between equal values regardless of order: the order constraint is exactly what makes this LCS.
  • Reusing an index in two lines: each index participates in at most one line.
  • Forgetting the shifted indices: dp[i][j] refers to nums1[i-1] and nums2[j-1], not i and j.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems