Uncrossed Lines — Solution in Python, Java & C++
Uncrossed Lines solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Uncrossed Lines is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Write nums1 on one line and nums2 on another. You may draw a connecting line between nums1[i] and nums2[j] when nums1[i] == nums2[j], provided no two lines cross and each number is used at most once.
Return the maximum number of connecting lines.
Example 1
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: Connect the 1s and then either the 4s or the 2s — connecting both would cross.
Example 2
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Example 3
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
Constraints
1 <= nums1.length, nums2.length <= 5001 <= nums1[i], nums2[j] <= 2000
Hints for Uncrossed Lines
Hint 1
Non-crossing means the connected indices must increase together on both lines.
Hint 2
That is precisely a common subsequence.
Hint 3
So the answer is the length of the longest common subsequence of the two arrays.
How to solve Uncrossed Lines
"No two lines cross" forces the matched index pairs to be increasing in both arrays — which is the definition of a common subsequence. The problem is LCS wearing a different hat.
Approach
- Let
dp[i][j]be the answer for the prefixesnums1[0..i)andnums2[0..j). - If the last elements match, connect them:
dp[i][j] = dp[i-1][j-1] + 1. - Otherwise take the better of dropping one element from either side.
- Return
dp[n][m].
Why it works
Two lines (i1, j1) and (i2, j2) cross exactly when i1 < i2 but j1 > j2. Forbidding that means the matched pairs form an increasing sequence in both index spaces — a common subsequence, whose maximum length the table computes.
Complexity
- Time —
O(n · m) - Space —
O(n · m), reducible to O(m)
Pitfalls
- Greedily connecting the first available equal pair can block a longer non-crossing set.
- Values may repeat, so counting shared values with a frequency map over-reports.
- The recurrence is the same as LCS on strings — the elements just happen to be integers.
Reference solution
Python
from typing import List
def maxUncrossedLines(nums1: List[int], nums2: List[int]) -> int:
n, m = len(nums1), len(nums2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 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[n][m]Java
public static int maxUncrossedLines(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}C++
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = (int) nums1.size(), m = (int) nums2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
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[n][m];
}JavaScript
var maxUncrossedLines = function(nums1, nums2) {
const n = nums1.length, m = nums2.length;
const dp = [];
for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (nums1[i - 1] === nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming