Uncrossed Lines solution and explanation
Google
9 more videos on this problem
Uncrossed Lines | Dynamic programming | Leetcode #1035Techdose · 18:34 · 21K views
Uncrossed Lines - Leetcode 1035 - PythonNeetCodeIO · 29:14 · 11K views
Uncrossed Lines | Microsoft, Amazon, Meta | Leetcode-1035 | Live Code + ExplanationcodestorywithMIK · 22:09 · 6K views
Uncrossed Lines | LeetCode 1035 | C++, Java, Python | May LeetCoding Day 25Knowledge Center · 23:56 · 3K views
uncrossed lines | uncrossed lines leetcode | uncrossed lines python | leetcode 1035thecodingworld · 15:32 · 3K views
Uncrossed Lines - Leetcode 1035 - PythonTechError · 11:44 · 1K views
1035. Uncrossed Lines (updated video in description) (Leetcode Medium)Programming Live with Larry · 13:13 · 1K views
1035. Uncrossed Lines | LCS | LeetCode Daily Challenge POTDDeep Tech · 15:02 · 729 views
Uncrossed Lines | Dynamic Programming | Leetcode 1035Nideesh Terapalli · 10:20 · 479 views
Uncrossed Lines Python - Leetcode 1035 | Algorithm ExplainedPersistent Programmer · 19:19 · 427 views
The problem
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:
nums1[i] == nums2[j], and- the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4] Output: 2 Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
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
Approach overview
Problem Overview: You are given two integer arrays. Draw lines connecting equal numbers between the arrays such that the lines do not cross. The goal is to compute the maximum number of such connections. The key observation: once two elements are matched, their relative order must remain consistent, otherwise the lines would intersect.
This constraint makes the problem identical to the Longest Common Subsequence (LCS) problem. You want the longest sequence of elements that appears in both arrays while preserving order. Every element in that subsequence represents one uncrossed line.
Approach 1: Dynamic Programming (LCS Table) (Time: O(n*m), Space: O(n*m))
Create a 2D DP table where dp[i][j] represents the maximum number of uncrossed lines you can draw using the first i elements of nums1 and the first j elements of nums2. Iterate through both arrays. If nums1[i-1] == nums2[j-1], you can connect them, so dp[i][j] = 1 + dp[i-1][j-1]. Otherwise, skip one element from either array: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This builds the optimal answer bottom‑up. The approach systematically explores all pair combinations and ensures order is preserved, preventing crossings. The final answer is stored in dp[n][m].
This method is straightforward and commonly used in interview settings because it clearly demonstrates understanding of dynamic programming. The table explicitly shows how partial solutions combine to form the final result.
Approach 2: Space Optimized Dynamic Programming (Time: O(n*m), Space: O(min(n,m)))
The full DP table is not always necessary. Each state only depends on the previous row and the current row. Instead of storing an n x m matrix, maintain two 1D arrays representing the previous and current rows. Iterate through nums1, and for each element update values across nums2. When the elements match, update using the diagonal value from the previous row; otherwise carry forward the maximum from adjacent states.
This optimization reduces memory usage significantly while preserving the same O(n*m) runtime. It is useful when arrays are large and memory limits matter. The logic remains identical to the classic LCS DP, but storage shrinks to linear space.
The problem is categorized under Array and Dynamic Programming because it combines sequential array traversal with optimal substructure reasoning. Once you recognize the LCS pattern, the solution becomes straightforward.
Recommended for interviews: The standard 2D dynamic programming solution is what interviewers typically expect. It clearly models the LCS recurrence and demonstrates strong DP fundamentals. Mentioning the space optimization afterward shows deeper understanding and awareness of memory tradeoffs.
Approach 1: Dynamic Programming Approach
This approach uses a dynamic programming (DP) solution where we maintain a 2D array called dp. The element dp[i][j] represents the maximum number of lines that can be drawn without crossing up to the i-th element of nums1 and the j-th element of nums2.
The DP formulation is based on: if nums1[i] == nums2[j], then dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
The final answer is found in dp[m][n], where m and n are the lengths of nums1 and nums2 respectively. This approach runs in O(m * n) time complexity and uses O(m * n) space.
def maxUncrossedLines(A, B):
m, n = len(A), len(B)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if A[i - 1] == B[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]
nums1 = [1, 4, 2]
nums2 = [1, 2, 4]
print("Output:", maxUncrossedLines(nums1, nums2))import java.util.*;
public class Solution {
public int maxUncrossedLines(int[] A, int[] B) {
int m = A.length, n = B.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i - 1] == B[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[m][n];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {1, 4, 2};
int[] nums2 = {1, 2, 4};
System.out.println("Output: " + solution.maxUncrossedLines(nums1, nums2));
}
}#include <vector>
#include <iostream>
using namespace std;
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int m = A.size(), n = B.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (A[i - 1] == B[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];
}
int main() {
vector<int> nums1 = {1, 4, 2};
vector<int> nums2 = {1, 2, 4};
cout << "Output: " << maxUncrossedLines(nums1, nums2) << endl;
return 0;
}function maxUncrossedLines(A, B) {
const m = A.length, n = B.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (A[i - 1] === B[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[m][n];
}
const nums1 = [1, 4, 2];
const nums2 = [1, 2, 4];
console.log("Output:", maxUncrossedLines(nums1, nums2));#include <stdio.h>
#include <string.h>
int maxUncrossedLines(int* A, int ASize, int* B, int BSize) {
int dp[ASize + 1][BSize + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= ASize; i++) {
for (int j = 1; j <= BSize; j++) {
if (A[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
}
}
return dp[ASize][BSize];
}
int main() {
int nums1[] = {1, 4, 2};
int nums2[] = {1, 2, 4};
int result = maxUncrossedLines(nums1, 3, nums2, 3);
printf("Output: %d\n", result);
return 0;
}using System;
public class Solution {
public int MaxUncrossedLines(int[] A, int[] B) {
int m = A.Length, n = B.Length;
int[,] dp = new int[m + 1, n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i - 1] == B[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[m, n];
}
public static void Main() {
Solution solution = new Solution();
int[] nums1 = {1, 4, 2};
int[] nums2 = {1, 2, 4};
Console.WriteLine("Output: " + solution.MaxUncrossedLines(nums1, nums2));
}
}The Python solution establishes a 2D list dp to track the best solution so far for subarrays of nums1 and nums2. The list is filled through nested loops by either incrementing the value when encountering matching elements from the two lists or propagating the maximum seen value otherwise.
Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2.
Space Complexity: O(m * n), for the dp list.
Approach 2: Space Optimized Dynamic Programming
This approach is an optimization of the basic dynamic programming solution by reducing space complexity. Instead of utilizing a 2D array, we can use a single-dimensional array to store only the current and previous row information, thus reducing the space usage. This takes advantage of the fact that the current DP state depends only on the previous state, not all preceding states.
We maintain two 1D arrays, and they get updated in each iteration over the second array, resulting in reduced space complexity to O(min(m, n)).
def maxUncrossedLines(A, B):
if len(A) < len(B):
A, B = B, A
m, n = len(A), len(B)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
temp = dp[j]
if A[i - 1] == B[j - 1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return dp[n]
nums1 = [1, 4, 2]
nums2 = [1, 2, 4]
print("Output:", maxUncrossedLines(nums1, nums2))import java.util.*;
public class Solution {
public int maxUncrossedLines(int[] A, int[] B) {
if (A.length < B.length) return maxUncrossedLines(B, A);
int m = A.length, n = B.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (A[i - 1] == B[j - 1])
dp[j] = prev + 1;
else
dp[j] = Math.max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[n];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums1 = {1, 4, 2};
int[] nums2 = {1, 2, 4};
System.out.println("Output: " + solution.maxUncrossedLines(nums1, nums2));
}
}#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
if (A.size() < B.size()) return maxUncrossedLines(B, A);
vector<int> dp(B.size() + 1, 0);
for (int i = 1; i <= A.size(); ++i) {
int prev = 0;
for (int j = 1; j <= B.size(); ++j) {
int temp = dp[j];
if (A[i - 1] == B[j - 1])
dp[j] = prev + 1;
else
dp[j] = max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[B.size()];
}
int main() {
vector<int> nums1 = {1, 4, 2};
vector<int> nums2 = {1, 2, 4};
cout << "Output: " << maxUncrossedLines(nums1, nums2) << endl;
return 0;
}function maxUncrossedLines(A, B) {
if (A.length < B.length) return maxUncrossedLines(B, A);
const m = A.length, n = B.length;
let dp = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
let prev = 0;
for (let j = 1; j <= n; j++) {
let temp = dp[j];
if (A[i - 1] === B[j - 1])
dp[j] = prev + 1;
else
dp[j] = Math.max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[n];
}
const nums1 = [1, 4, 2];
const nums2 = [1, 2, 4];
console.log("Output:", maxUncrossedLines(nums1, nums2));#include <stdio.h>
#include <string.h>
int maxUncrossedLines(int* A, int ASize, int* B, int BSize) {
if (ASize < BSize) return maxUncrossedLines(B, BSize, A, ASize);
int dp[BSize + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= ASize; i++) {
int prev = 0;
for (int j = 1; j <= BSize; j++) {
int cur = dp[j];
if (A[i - 1] == B[j - 1])
dp[j] = prev + 1;
else
dp[j] = (dp[j] > dp[j - 1]) ? dp[j] : dp[j - 1];
prev = cur;
}
}
return dp[BSize];
}
int main() {
int nums1[] = {1, 4, 2};
int nums2[] = {1, 2, 4};
int result = maxUncrossedLines(nums1, 3, nums2, 3);
printf("Output: %d\n", result);
return 0;
}using System;
public class Solution {
public int MaxUncrossedLines(int[] A, int[] B) {
if (A.Length < B.Length) return MaxUncrossedLines(B, A);
int m = A.Length, n = B.Length;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (A[i - 1] == B[j - 1])
dp[j] = prev + 1;
else
dp[j] = Math.Max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[n];
}
public static void Main() {
Solution solution = new Solution();
int[] nums1 = {1, 4, 2};
int[] nums2 = {1, 2, 4};
Console.WriteLine("Output: " + solution.MaxUncrossedLines(nums1, nums2));
}
}The Pythonic pattern for reduced-space usage involves a single iterative array dp, which records ongoing state progress throughout the arrays. Element matching prompts state advancement, while non-matching elements rely on propagated maxima for determining sequence continuity.
Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2.
Space Complexity: O(min(m, n)), for the dp array.
Approach 3: Dynamic Programming
We define f[i][j] to represent the maximum number of connections between the first i numbers of nums1 and the first j numbers of nums2. Initially, f[i][j] = 0, and the answer is f[m][n].
When nums1[i-1] = nums2[j-1], we can add a connection based on the first i-1 numbers of nums1 and the first j-1 numbers of nums2. In this case, f[i][j] = f[i-1][j-1] + 1.
When nums1[i-1] neq nums2[j-1], we either solve based on the first i-1 numbers of nums1 and the first j numbers of nums2, or solve based on the first i numbers of nums1 and the first j-1 numbers of nums2, taking the maximum of the two. That is, f[i][j] = max(f[i-1][j], f[i][j-1]).
Finally, return f[m][n].
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of nums1 and nums2, respectively.
function maxUncrossedLines(nums1: number[], nums2: number[]): number {
const m = nums1.length;
const n = nums2.length;
const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (nums1[i - 1] === nums2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[m][n];
}func maxUncrossedLines(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
f[i][j] = f[i-1][j-1] + 1
} else {
f[i][j] = max(f[i-1][j], f[i][j-1])
}
}
}
return f[m][n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2. |
| Space Optimized Dynamic Programming | Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (LCS Table) | O(n*m) | O(n*m) | Best for clarity and interviews. Easy to reason about and implement. |
| Space Optimized Dynamic Programming | O(n*m) | O(min(n,m)) | Use when arrays are large and memory usage must be minimized. |
Frequently asked questions
Is Uncrossed Lines easy or hard?
Uncrossed Lines is considered a medium-level problem on LeetCode. The challenge is recognizing that the constraint about non-crossing lines maps directly to the Longest Common Subsequence dynamic programming pattern.
How to solve Uncrossed Lines in O(n)?
A true O(n) solution does not exist for the general case because every element of one array may need to be compared with every element of the other. The optimal solution uses dynamic programming with O(n*m) time. Space can be reduced to O(min(n,m)) using a rolling array optimization.
What is the best approach for Uncrossed Lines?
The best approach is dynamic programming using the Longest Common Subsequence (LCS) technique. You build a DP table where dp[i][j] represents the maximum uncrossed lines using the first i elements of nums1 and j elements of nums2. This guarantees an optimal solution with O(n*m) time complexity.
Is Uncrossed Lines asked at Google/Amazon/Meta?
Problems based on Longest Common Subsequence and dynamic programming frequently appear in interviews at companies like Amazon, Google, and Meta. Uncrossed Lines is a direct LCS variation, making it a strong practice problem for those interview patterns.
What data structure is used in Uncrossed Lines?
The solution mainly uses arrays to store dynamic programming states. A 2D matrix (or optimized 1D arrays) keeps track of the best results for subproblems while iterating through both input arrays.
What is the time complexity of Uncrossed Lines?
The standard dynamic programming solution runs in O(n*m) time where n and m are the lengths of the two arrays. Each pair of indices is processed once while filling the DP table. Space complexity is O(n*m) or O(min(n,m)) with the optimized version.
Uncrossed Lines Python or Java solution approach?
Both Python and Java implementations follow the same LCS dynamic programming pattern. Create a DP table, iterate through both arrays, update matches using dp[i-1][j-1] + 1, and propagate maximum values for mismatches. The final DP cell gives the number of uncrossed lines.