# Uncrossed Lines

### **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*.

**Link:** [https://leetcode.com/problems/uncrossed-lines/description/](https://leetcode.com/problems/uncrossed-lines/description/)

### **Problem Explanation with examples:-**

**Example 1**

```markdown
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**

```markdown
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Explanation: There can only be 3 connections without crossing the lines. nums1[0]=2 connects to nums2[2]=2, nums1[1]=5 connects to nums2[4]=5, and nums1[3]=2 connects to nums2[5]=2.
```

**Example 3**

```markdown
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
Explanation: There can only be 2 connections without crossing the lines. nums1[0]=1 connects to nums2[4]=1, and nums1[5]=5 connects to nums2[3]=5.
```

**Constraints**

* `1 <= nums1.length, nums2.length <= 500`
    
* `1 <= nums1[i], nums2[j] <= 2000`
    

### Intuition:-

* If one element connects to some equal in the other array then the indexes previous to that element in both the arrays are of no more use to us.
    
* We can use dp by keeping a pointer in both arrays and then we can either connect an equal element or we can skip the element in the first array.
    

### Solution:-

* Take the length of both the arrays in variables m and n.
    
* Define a function solve(i,j) which returns the maximum number of lines that can be drawn without crossing each other if we start from index i in the first array and index j in the second array.
    
* If i &gt;= m or j &gt;= n then return 0.
    
* Keep a variable mx to store the maximum number of lines that can be drawn.
    
* Loop over from j to n and check if nums1\[i\] == nums2\[z\] then update mx = max(mx,1+solve(i+1,z+1)).
    
* Update mx = max(mx,solve(i+1,j)) to account for the case when we skip the element in the first array.
    
* Return mx.
    

### Code:-

JAVA Solution

```java
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        HashMap<String, Integer> memo = new HashMap<>();
        
        return solve(nums1, nums2, 0, 0, memo);
    }
    
    private int solve(int[] nums1, int[] nums2, int i, int j, HashMap<String, Integer> memo) {
        if (i >= nums1.length || j >= nums2.length) {
            return 0;
        }
        
        String key = i + "," + j;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int mx = 0;
        for (int z = j; z < nums2.length; z++) {
            if (nums1[i] == nums2[z]) {
                mx = Math.max(mx, 1 + solve(nums1, nums2, i + 1, z + 1, memo));
            }
        }
        
        mx = Math.max(mx, solve(nums1, nums2, i + 1, j, memo));
        
        memo.put(key, mx);
        return mx;
    }
}
```

Python Solution

```python
class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        @cache
        def solve(i,j):
            if i >= m or j >= n:
                return 0
            mx = 0
            for z in range(j,n):
                if nums1[i] == nums2[z]:
                    mx = max(mx,1+solve(i+1,z+1))

            mx = max(mx,solve(i+1,j))

            return mx

        return solve(0,0)
```

### Complexity Analysis:-

**TIME**:-

The time complexity is **O(m\*n)**, where m and n are the lengths of nums1 and nums2, respectively. This is because we have to evaluate the function for all possible i and j values between 0 and m-1 and n-1, respectively.

**SPACE**:-

The space complexity is **O(m*n)****, due to the use of memoization using the @cache decorator. The cache will store the results of all unique (i,j) combinations, which can be at most m*n.

### References:-

* [**Recursion**](https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/)
    
* [**DP**](https://www.geeksforgeeks.org/dynamic-programming/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)