Uncrossed Lines
MedPrompt
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: 3Example 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
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's recursive structure into code. The problem of finding the maximum number of uncrossed lines can be broken down into smaller, similar subproblems. We define a function that calculates the maximum uncrossed lines for suffixes of the original arrays. The function considers two cases at each step: either the current elements match, or they don't. This leads to an exponential number of redundant calculations for the same subproblems, making it highly inefficient.
Algorithm
- Define a recursive function
solve(i, j)that computes the maximum number of uncrossed lines fornums1starting from indexiandnums2starting from indexj. - Base Case: If
iorjgoes beyond the array bounds, it means we have exhausted one of the arrays, so no more lines can be drawn. Return 0. - Recursive Step:
- If
nums1[i] == nums2[j]: A line can be drawn. The result is1 + solve(i + 1, j + 1). - If
nums1[i] != nums2[j]: No line can be drawn. We must choose the better of two options: skipping the element innums1(solve(i + 1, j)) or skipping the element innums2(solve(i, j + 1)). The result ismax(solve(i + 1, j), solve(i, j + 1)).
- If
- The initial call to start the process is
solve(0, 0).
Walkthrough
The core idea is to recognize the problem's recursive nature. Let's define a function, say solve(i, j), which computes the maximum number of uncrossed lines for nums1 starting from index i and nums2 starting from index j.
-
Base Case: If
ireaches the end ofnums1orjreaches the end ofnums2, we can't draw any more lines. So, we return 0. -
Recursive Step:
- If
nums1[i] == nums2[j]: We have found a pair of equal numbers. We can draw a line between them. This line contributes 1 to our count. The non-crossing constraint means we must then look for more lines in the remaining parts of the arrays, i.e.,nums1[i+1...]andnums2[j+1...]. The total is1 + solve(i + 1, j + 1). - If
nums1[i] != nums2[j]: We cannot draw a line between the current elements. We have two choices to maximize our count:- Skip the current element in
nums1and find the maximum lines fromnums1[i+1...]andnums2[j...]. This corresponds tosolve(i + 1, j). - Skip the current element in
nums2and find the maximum lines fromnums1[i...]andnums2[j+1...]. This corresponds tosolve(i, j + 1). We take the maximum of these two choices to get the optimal solution for the current state.
- Skip the current element in
- If
The final answer is obtained by calling solve(0, 0).
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { return solve(nums1, nums2, 0, 0); } private int solve(int[] nums1, int[] nums2, int i, int j) { if (i >= nums1.length || j >= nums2.length) { return 0; } if (nums1[i] == nums2[j]) { return 1 + solve(nums1, nums2, i + 1, j + 1); } else { int option1 = solve(nums1, nums2, i + 1, j); int option2 = solve(nums1, nums2, i, j + 1); return Math.max(option1, option2); } }}Complexity
Time
O(2^(m+n)). In the worst case, the recursion tree branches into two at each step where elements don't match, leading to an exponential number of calls.
Space
O(m + n), where m and n are the lengths of the arrays. This space is used by the recursion call stack.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem's definition.
Cons
Extremely inefficient due to a massive number of overlapping subproblems being re-calculated.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for all but the smallest inputs.
This approach, also known as Top-Down Dynamic Programming, optimizes the brute-force recursion by eliminating redundant computations. It uses a cache (a 2D array often called a memoization table) to store the results of subproblems that have already been solved. When the function is called with the same arguments again, it retrieves the result from the cache in constant time instead of re-computing it. This drastically reduces the time complexity from exponential to polynomial.
Algorithm
- The recursive structure is the same as the brute-force approach.
- Create a 2D array
memo[m][n]and initialize it with a value like -1 to indicate that a subproblem's result is not yet computed. - In the recursive function
solve(i, j): a. Check ifmemo[i][j]is not -1. If it's already computed, return the stored valuememo[i][j]. b. Otherwise, compute the result as in the brute-force approach. c. Before returning, store the computed result inmemo[i][j]. - The initial call remains
solve(0, 0).
Walkthrough
We identify that the brute-force approach repeatedly solves the same subproblems solve(i, j) for identical pairs of (i, j). Memoization is the technique to fix this.
We introduce a 2D array, memo[m][n], where m and n are the lengths of the input arrays. memo[i][j] will store the result of solve(i, j). This table is initialized with a sentinel value (e.g., -1) to signify that a state has not been computed.
Inside the recursive function solve(i, j), before any computation, we first check if memo[i][j] has been computed (i.e., its value is not -1). If it has, we return the stored value immediately. If not, we perform the same calculations as in the brute-force approach to find the result. Crucially, before returning this newly computed result, we store it in memo[i][j] so it can be reused later.
This ensures that each unique subproblem (i, j) is computed exactly once.
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[][] memo = new int[m][n]; for (int[] row : memo) { java.util.Arrays.fill(row, -1); } return solve(nums1, nums2, 0, 0, memo); } private int solve(int[] nums1, int[] nums2, int i, int j, int[][] memo) { if (i >= nums1.length || j >= nums2.length) { return 0; } if (memo[i][j] != -1) { return memo[i][j]; } int result; if (nums1[i] == nums2[j]) { result = 1 + solve(nums1, nums2, i + 1, j + 1, memo); } else { int option1 = solve(nums1, nums2, i + 1, j, memo); int option2 = solve(nums1, nums2, i, j + 1, memo); result = Math.max(option1, option2); } memo[i][j] = result; return result; }}Complexity
Time
O(m * n). Each of the m*n possible states (i, j) is computed exactly once.
Space
O(m * n) for the memoization table. The recursion stack also contributes O(m+n), but this is dominated by the table size.
Trade-offs
Pros
Guarantees that each subproblem is solved only once, making it much more efficient than brute-force.
The code structure remains very similar to the pure recursive solution, making it relatively easy to implement.
Cons
Uses O(m*n) space for the memoization table.
Can cause a stack overflow for very deep recursion, though the problem constraints (lengths <= 500) make this unlikely.
This approach, also known as Bottom-Up Dynamic Programming, solves the problem iteratively, eliminating recursion entirely. It builds a 2D table (or matrix), dp, where dp[i][j] represents the maximum number of uncrossed lines using the first i elements of nums1 and the first j elements of nums2. The table is filled starting from the smallest subproblems, and each cell's value is computed based on previously computed values. This problem is a classic example of the Longest Common Subsequence (LCS) problem, and this is the standard tabular solution for it.
Algorithm
- Let
m = nums1.length,n = nums2.length. - Create a 2D array
dp[m+1][n+1]and initialize it with 0s.dp[i][j]will store the answer for prefixesnums1[0...i-1]andnums2[0...j-1]. - Iterate
ifrom 1 tom. - Iterate
jfrom 1 ton. -
If `nums1[i-1] == nums2[j-1]` (note the `i-1`, `j-1` due to 1-based DP indexing): -
`dp[i][j] = 1 + dp[i-1][j-1]`. -
Else: -
`dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. - The final answer is the value in the bottom-right cell,
dp[m][n].
Walkthrough
We can rephrase the problem as finding the Longest Common Subsequence (LCS) of nums1 and nums2. The non-crossing condition ensures that if we match nums1[i] with nums2[j], any subsequent match must involve indices greater than i and j.
We create a 2D DP table, dp, of size (m+1) x (n+1). The entry dp[i][j] will store the length of the LCS between the prefix nums1[0...i-1] and nums2[0...j-1]. The extra row and column are for convenience to handle the base cases where one of the prefixes is empty.
We fill the table iteratively:
- We loop from
i = 1tomandj = 1ton. - For each cell
dp[i][j], we comparenums1[i-1]andnums2[j-1]:- If they are equal, it means we found a new element for our common subsequence. We can extend the LCS of the prefixes ending at
i-1andj-1. Thus,dp[i][j] = 1 + dp[i-1][j-1]. - If they are not equal, we cannot extend the subsequence with the current pair. The LCS must be the same as the LCS of a smaller subproblem. We take the maximum of either excluding
nums1[i-1](givingdp[i-1][j]) or excludingnums2[j-1](givingdp[i][j-1]). Thus,dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- If they are equal, it means we found a new element for our common subsequence. We can extend the LCS of the prefixes ending at
After the loops complete, dp[m][n] holds the LCS length for the entire arrays, which is our answer.
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }}Complexity
Time
O(m * n). We iterate through each cell of the `m x n` DP table exactly once.
Space
O(m * n) to store the 2D DP table.
Trade-offs
Pros
Efficient and avoids recursion, thus preventing any potential stack overflow issues.
The iterative nature can sometimes be easier to reason about and debug than recursion.
Cons
Uses O(m*n) space, which can be substantial for large inputs, although it fits within the problem's constraints.
This approach optimizes the space complexity of the standard bottom-up DP solution. By observing the recurrence relation (dp[i][j] only depends on values from row i-1 and i), we realize that we don't need to store the entire 2D table. We only need to keep track of the previous row's results to compute the current row. This allows us to reduce the space from O(m*n) to O(min(m, n)) by using only two 1D arrays (or even a single 1D array with careful updates), making it the most efficient solution in terms of both time and space.
Algorithm
- Let
m = nums1.length,n = nums2.length. To optimize, ensurenis the smaller dimension (swap arrays if needed). - Create two 1D arrays,
prev[n+1]andcurr[n+1], initialized to 0.prevstores the DP results for the previous row (i-1), andcurrfor the current row (i). - Iterate
ifrom 1 tom. - Iterate
jfrom 1 ton. -
If `nums1[i-1] == nums2[j-1]`: -
`curr[j] = 1 + prev[j-1]`. -
Else: -
`curr[j] = max(prev[j], curr[j-1])`. - After the inner loop finishes, the
currarray is complete for rowi. Copy its contents toprevfor the next iteration (e.g.,prev = curr.clone()or by swapping array references). - After the outer loop, the answer is the last element of the final row,
prev[n].
Walkthrough
In the bottom-up DP approach, the calculation of dp[i][j] only depends on values from the current row i (dp[i][j-1]) and the previous row i-1 (dp[i-1][j] and dp[i-1][j-1]). This means we don't need to keep all m rows in memory at once.
We can optimize the space to use just two 1D arrays, let's call them prev and curr, each of size n+1 (where n is the length of the shorter array to minimize space). prev will hold the DP values for row i-1, and curr will be used to compute the values for row i.
We iterate i from 1 to m. In the inner loop (for j), we compute curr[j] using values from prev and curr[j-1]. After the inner loop completes for a given i, the curr array now holds the complete DP values for row i. We then make this curr array the prev array for the next iteration (i+1). This can be done by copying the array or simply swapping the references to the two arrays.
This reduces the space complexity to O(n) without affecting the O(m*n) time complexity.
class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; // Ensure nums2 is the shorter array to optimize space. if (m < n) { return maxUncrossedLines(nums2, nums1); } int[] prev = new int[n + 1]; int[] curr = new int[n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (nums1[i - 1] == nums2[j - 1]) { curr[j] = 1 + prev[j - 1]; } else { curr[j] = Math.max(prev[j], curr[j - 1]); } } // Prepare for the next row int[] temp = prev; prev = curr; curr = temp; // Old prev array is now curr, ready to be overwritten } return prev[n]; // prev holds the results of the last completed row }}Complexity
Time
O(m * n). The nested loop structure for filling the table remains the same.
Space
O(min(m, n)). We use 1D arrays whose size is determined by the length of the shorter of the two input arrays.
Trade-offs
Pros
Most efficient solution, optimal in both time and space.
Retains the O(m*n) time complexity while significantly reducing space usage.
Cons
The logic, especially with further optimization to a single array, can be slightly harder to grasp initially compared to the straightforward 2D table version.
Solutions
Solution
class Solution { public int maxUncrossedLines ( int [] nums1 , int [] nums2 ) { int m = nums1 . length ; int n = nums2 . length ; int [][] dp = new int [ m + 1 ][ n + 1 ]; for ( int i = 1 ; i <= m ; i ++) { for ( int j = 1 ; j <= n ; 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 [ m ][ n ]; } }/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var maxUncrossedLines = function (nums1, nums2) { const m = nums1.length; const n = nums2.length; const f = 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]; };class Solution { public: int maxUncrossedLines ( vector < int >& nums1 , vector < int >& nums2 ) { int m = nums1 . size (), n = nums2 . size (); vector < vector < int >> dp ( m + 1 , vector < int > ( n + 1 )); for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = 1 ; j <= n ; ++ 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 [ m ][ n ]; } };class Solution : def maxUncrossedLines ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : m , n = len ( nums1 ), len ( nums2 ) dp = [[ 0 ] * ( n + 1 ) for i 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 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.