Uncrossed Lines
Uncrossed Lines: draw lines connecting equal values in nums1 and nums2 so that no two lines cross, and return the maximum number of lines you can draw.
- 1 <= nums1.length, nums2.length <= 500
- 1 <= nums1[i], nums2[j] <= 2000
Intuition
Lines may not cross, which means the connected pairs must appear in the same relative order in both arrays. That is precisely the definition of a common subsequence — so the largest set of uncrossed lines is the Longest Common Subsequence of the two arrays, and the familiar LCS table solves it unchanged.
The tell is a geometric or ordering constraint that quietly forbids reordering — 'lines must not cross', 'pairs must stay in sequence'. Whenever matched elements have to preserve relative order in both inputs, it is LCS in disguise. Recognising the disguise is the whole difficulty here; the recurrence itself is standard and identical to Longest Common Subsequence and Delete Operation for Two Strings.
Approach
Before reading on: draw two lines that cross and look at the index pairs they use. What ordering property must every pair of non-crossing lines satisfy? Name the classic problem that property defines. Aim for O(m·n).
Why 'no crossing' means 'same order'
Suppose you connect nums1[i] to nums2[j], and also nums1[k] to nums2[l]. These two lines avoid crossing exactly when the pairs keep the same relative order — if i < k then j < l must hold too, otherwise the segments intersect. Extend that to every pair of lines and the whole set of connections is an increasing sequence of index pairs matching equal values. Reading off the matched values gives a sequence that appears, in order, in both arrays: a common subsequence. Maximising lines therefore means finding the longest one.
The LCS recurrence
Let dp[i][j] be the answer for the first i elements of nums1 and the first j of nums2. If nums1[i-1] == nums2[j-1], those two values can be joined by a line that crosses nothing already counted, so dp[i][j] = 1 + dp[i-1][j-1] — take the match and shrink both sides. If they differ, no line can join this particular pair, so the best is whichever gives more: discard the last element of nums1, or of nums2, giving dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Row 0 and column 0 are all zeros, since an empty prefix supports no lines.
Filling the table and reading the answer
Iterate i from 1 to m and j from 1 to n, applying the two cases. Each cell is O(1) and depends only on cells above, to the left, and diagonally up-left, so a single forward pass fills the table correctly. dp[m][n] — the bottom-right corner — is the answer for the complete arrays. Time is O(m·n) and space is O(m·n); because every row depends only on the previous one, the table can be collapsed to two rows for O(min(m, n)) space when memory matters.
Solution & live demo
Common pitfalls
Counting shared values instead of a subsequence
return len(set(nums1) & set(nums2))
dp[i][j] = 1 + dp[i - 1][j - 1] # when values match
Set intersection ignores both order and multiplicity. On nums1 = [1,2] and nums2 = [2,1] it returns 2, but any two such lines must cross, so the true answer is 1.
Off-by-one between table and array indices
if nums1[i] == nums2[j]:
dp[i][j] = 1 + dp[i-1][j-1]if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]The table is padded with a zero row and column, so dp[i][j] describes the first i and j elements — the values it compares are at i-1 and j-1. Indexing directly with i and j reads one element too far and throws or silently misaligns.
Taking the max even when the values match
dp[i][j] = max(dp[i-1][j], dp[i][j-1], 1 + dp[i-1][j-1])
if nums1[i-1] == nums2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])It happens to return the right number but obscures the reasoning and does extra work. When the ends match, taking that line is always at least as good as skipping it — there is no trade-off to evaluate, which is why the branch is clean.
Edge cases
No match ever fires, so every cell takes the max of its neighbours and the table stays 0 — the answer is 0.
The diagonal step consumes one element from each side per match, so a value cannot be reused and the count stays correct at 2.
Every element of the shorter array matches in order, so the answer equals its length.
The table is rectangular (m+1) × (n+1); the recurrence never assumes m equals n.