# Uncrossed Lines
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/uncrossed-lines)
Canonical: https://scaleengineer.com/dsa/problems/uncrossed-lines
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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:**

![](https://assets.glich.co/dsa/uncrossed-lines/image0.png) 

**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 <= 500`
* `1 <= nums1[i], nums2[j] <= 2000`

# Approaches
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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 `i` reaches the end of `nums1` or `j` reaches the end of `nums2`, 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...]` and `nums2[j+1...]`. The total is `1 + 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:
    1. Skip the current element in `nums1` and find the maximum lines from `nums1[i+1...]` and `nums2[j...]`. This corresponds to `solve(i + 1, j)`.
    2. Skip the current element in `nums2` and find the maximum lines from `nums1[i...]` and `nums2[j+1...]`. This corresponds to `solve(i, j + 1)`.
  We take the maximum of these two choices to get the optimal solution for the current state.

The final answer is obtained by calling `solve(0, 0)`.

```java
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);
        }
    }
}
```
### Algorithm
1. Define a recursive function `solve(i, j)` that computes the maximum number of uncrossed lines for `nums1` starting from index `i` and `nums2` starting from index `j`.
2. **Base Case:** If `i` or `j` goes beyond the array bounds, it means we have exhausted one of the arrays, so no more lines can be drawn. Return 0.
3. **Recursive Step:**
    - If `nums1[i] == nums2[j]`: A line can be drawn. The result is `1 + 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 in `nums1` (`solve(i + 1, j)`) or skipping the element in `nums2` (`solve(i, j + 1)`). The result is `max(solve(i + 1, j), solve(i, j + 1))`.
4. The initial call to start the process is `solve(0, 0)`.

## Top-Down Dynamic Programming (Memoization)
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. The recursive structure is the same as the brute-force approach.
2. 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.
3. In the recursive function `solve(i, j)`:
    a. Check if `memo[i][j]` is not -1. If it's already computed, return the stored value `memo[i][j]`.
    b. Otherwise, compute the result as in the brute-force approach.
    c. Before returning, store the computed result in `memo[i][j]`.
4. The initial call remains `solve(0, 0)`.

## Bottom-Up Dynamic Programming (Tabulation)
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.
**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.
**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.
### Explanation
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 = 1` to `m` and `j = 1` to `n`.
- For each cell `dp[i][j]`, we compare `nums1[i-1]` and `nums2[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-1` and `j-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]` (giving `dp[i-1][j]`) or excluding `nums2[j-1]` (giving `dp[i][j-1]`). Thus, `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`.

After the loops complete, `dp[m][n]` holds the LCS length for the entire arrays, which is our answer.

```java
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];
    }
}
```
### Algorithm
1. Let `m = nums1.length`, `n = nums2.length`.
2. Create a 2D array `dp[m+1][n+1]` and initialize it with 0s. `dp[i][j]` will store the answer for prefixes `nums1[0...i-1]` and `nums2[0...j-1]`.
3. Iterate `i` from 1 to `m`.
4.   Iterate `j` from 1 to `n`.
5.     If `nums1[i-1] == nums2[j-1]` (note the `i-1`, `j-1` due to 1-based DP indexing):
6.       `dp[i][j] = 1 + dp[i-1][j-1]`.
7.     Else:
8.       `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`.
9. The final answer is the value in the bottom-right cell, `dp[m][n]`.

## Space-Optimized Bottom-Up Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
1. Let `m = nums1.length`, `n = nums2.length`. To optimize, ensure `n` is the smaller dimension (swap arrays if needed).
2. Create two 1D arrays, `prev[n+1]` and `curr[n+1]`, initialized to 0. `prev` stores the DP results for the previous row (`i-1`), and `curr` for the current row (`i`).
3. Iterate `i` from 1 to `m`.
4.   Iterate `j` from 1 to `n`.
5.     If `nums1[i-1] == nums2[j-1]`:
6.       `curr[j] = 1 + prev[j-1]`.
7.     Else:
8.       `curr[j] = max(prev[j], curr[j-1])`.
9.   After the inner loop finishes, the `curr` array is complete for row `i`. Copy its contents to `prev` for the next iteration (e.g., `prev = curr.clone()` or by swapping array references).
10. After the outer loop, the answer is the last element of the final row, `prev[n]`.

# Solutions
### Java

```java
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 ]; } }
```

### JavaScript

```javascript
/** * @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];
  };

```

### CPP

```cpp
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 ]; } };
```

### Python

```python
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 ]
```