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
- The order-preserving, non-crossing constraint makes this identical to the longest common subsequence problem.
- Let
dp[i][j]be the maximum number of lines using the firstielements ofnums1and the firstjofnums2. - If
nums1[i-1] == nums2[j-1], extend the diagonal:dp[i][j] = dp[i-1][j-1] + 1. - 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 tonums1[i-1]andnums2[j-1], notiandj.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.