# LeetCode 1035: Uncrossed Lines

## Problem Restatement

We are given two integer arrays `nums1` and `nums2`.

We draw lines connecting equal values: `nums1[i]` to `nums2[j]` when `nums1[i] == nums2[j]`.

Two lines cannot cross.

We need to return the maximum number of connecting lines we can draw without any crossing.

The official constraints state that `1 <= nums1.length, nums2.length <= 500` and `1 <= nums1[i], nums2[j] <= 2000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Arrays `nums1` and `nums2` |
| Output | Maximum number of uncrossed lines |

Function shape:

```python
def maxUncrossedLines(nums1: list[int], nums2: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums1 = [1, 4, 2]
nums2 = [1, 2, 4]
```

We can connect `1-1` and `4-4`: two lines, and they don't cross.

Answer:

```python
2
```

Example 2:

```python
nums1 = [2, 5, 1, 2, 5]
nums2 = [10, 5, 2, 1, 5, 2]
```

Maximum uncrossed lines: `3`.

Answer:

```python
3
```

## Key Insight

Two connecting lines do not cross if and only if the connected pairs form a subsequence in both arrays.

This is exactly the **Longest Common Subsequence (LCS)** problem.

## Algorithm

Standard LCS DP:

```python
dp[i][j] = LCS length of nums1[:i] and nums2[:j]
```

Transition:
- 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])`.

## Correctness

Two lines from `nums1[i]` to `nums2[j]` and `nums1[i']` to `nums2[j']` do not cross if and only if `i < i'` implies `j < j'`. This is exactly the condition for an increasing subsequence — the LCS.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

Let `m = len(nums1)` and `n = len(nums2)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | Fill the DP table |
| Space | `O(m * n)` | DP table (or `O(n)` with rolling array) |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def maxUncrossedLines(self, nums1: list[int], nums2: list[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ 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]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxUncrossedLines([1,4,2], [1,2,4]) == 2
    assert s.maxUncrossedLines([2,5,1,2,5], [10,5,2,1,5,2]) == 3
    assert s.maxUncrossedLines([1,3,7,1,7,5], [1,9,2,5,1]) == 2

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[1,4,2]` vs `[1,2,4]` | `2` | LCS is `[1,4]` or `[1,2]` |
| 5 vs 6 elements | `3` | Three common elements in order |
| 6 vs 5 elements | `2` | LCS of length 2 |