Uncrossed Lines - Solution & Explanation
Problem Statement
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.
The C solution uses a 2D array dp which is initialized to zero and filled using a nested loop. For each pair of elements in nums1 and nums2, if they are equal, we increment the value from diagonally top-left in the dp array and store it in the current cell. If they are not equal, we take the maximum value from either directly above or to the left of the current cell. This ensures that we are keeping track of the longest sequence of lines possible up to the current elements.
Complexity
Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2.
Space Complexity: O(m * n), for the dp array.
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)).
By leveraging a single array dp of size equal to nums2, the solution benefits from reduced space usage. We keep track of the previous computed value using a temporary variable prev. For each element pair, we determine the longest line by either incrementing based on a match or preserving the maximum from prior positions.
Complexity
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.
Code
Python
Java
C++
Go
TypeScript
JavaScript
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 | — |
Detailed 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. |
Video Solution
Uncrossed Lines | Dynamic programming | Leetcode #1035 • Techdose • 21,162 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Uncrossed Lines easy or hard?
How to solve Uncrossed Lines in O(n)?
What is the best approach for Uncrossed Lines?
Is Uncrossed Lines asked at Google/Amazon/Meta?
What data structure is used in Uncrossed Lines?
What is the time complexity of Uncrossed Lines?
Uncrossed Lines Python or Java solution approach?
Ready to solve this problem?
Practice Uncrossed Lines with our built-in code editor and test cases.
Practice on FleetCode