# LeetCode 718: Maximum Length of Repeated Subarray

## Problem Restatement

We are given two integer arrays:

```python
nums1
nums2
```

We need to return the maximum length of a subarray that appears in both arrays.

A subarray is contiguous.

That means we cannot skip elements.

For example:

```python
[3, 2, 1]
```

is a subarray of:

```python
[1, 2, 3, 2, 1]
```

only if those values appear next to each other in that exact order.

The official statement asks for the maximum length of a subarray that appears in both arrays. Example 1 uses `nums1 = [1,2,3,2,1]` and `nums2 = [3,2,1,4,7]`, where the answer is `3` for `[3,2,1]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums1` |
| Input | Integer array `nums2` |
| Output | Length of the longest common subarray |
| Important detail | The match must be contiguous |
| If no common value exists | Return `0` |

The function shape is:

```python
class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        ...
```

## Examples

Example 1:

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

The longest common subarray is:

```python
[3, 2, 1]
```

Its length is:

```python
3
```

Output:

```python
3
```

Example 2:

```python
nums1 = [0, 0, 0, 0, 0]
nums2 = [0, 0, 0, 0, 0]
```

The whole array appears in both arrays.

Output:

```python
5
```

## First Thought: Try Every Pair of Starts

A direct approach is to try every starting index in both arrays.

For every pair:

```python
i in nums1
j in nums2
```

we compare forward while the values match.

```python
nums1[i] == nums2[j]
nums1[i + 1] == nums2[j + 1]
...
```

This works, but it repeats many comparisons.

In the worst case, many values are equal, so the same matching suffixes are checked again and again.

## Problem With Brute Force

If both arrays have length `n`, there are `O(n^2)` pairs of starting indices.

For each pair, we may compare up to `O(n)` elements.

So the brute force runtime can become:

```python
O(n^3)
```

We need to reuse previous matching work.

## Key Insight

This is similar to longest common substring, but for arrays.

Define:

```python
dp[i][j]
```

as the length of the longest common subarray ending at:

```python
nums1[i - 1]
nums2[j - 1]
```

If the two ending values match, then we can extend the previous common subarray:

```python
dp[i][j] = dp[i - 1][j - 1] + 1
```

If the two ending values do not match, then no common subarray can end at both positions:

```python
dp[i][j] = 0
```

The answer is the maximum value in the DP table.

## Algorithm

Let:

```python
m = len(nums1)
n = len(nums2)
```

Create a DP table:

```python
dp = [[0] * (n + 1) for _ in range(m + 1)]
```

Then:

1. Initialize `answer = 0`.
2. For each `i` from `1` to `m`:
   - For each `j` from `1` to `n`:
     - If `nums1[i - 1] == nums2[j - 1]`, set `dp[i][j] = dp[i - 1][j - 1] + 1`.
     - Update `answer`.
     - If they differ, leave `dp[i][j] = 0`.
3. Return `answer`.

## Correctness

We prove that `dp[i][j]` stores the length of the longest common subarray ending exactly at `nums1[i - 1]` and `nums2[j - 1]`.

If `nums1[i - 1] != nums2[j - 1]`, then no common subarray can end at both positions, because the final elements differ. So `dp[i][j] = 0` is correct.

If `nums1[i - 1] == nums2[j - 1]`, then any common subarray ending at these two positions must extend a common subarray ending at `nums1[i - 2]` and `nums2[j - 2]`. The longest such previous subarray has length `dp[i - 1][j - 1]`, so the new length is `dp[i - 1][j - 1] + 1`.

The algorithm computes every pair of ending positions. Every repeated subarray has some ending position in both arrays, so its length appears in the DP table. Taking the maximum over all states gives the length of the longest repeated subarray.

## Complexity

Let:

```python
m = len(nums1)
n = len(nums2)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(mn)` | We compute one state for every pair of positions |
| Space | `O(mn)` | The DP table has `(m + 1)(n + 1)` cells |

## Implementation

```python
class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        m = len(nums1)
        n = len(nums2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]
        answer = 0

        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
                    answer = max(answer, dp[i][j])

        return answer
```

## Code Explanation

We create one extra row and one extra column:

```python
dp = [[0] * (n + 1) for _ in range(m + 1)]
```

This avoids boundary checks when `i = 1` or `j = 1`.

For each pair of positions:

```python
if nums1[i - 1] == nums2[j - 1]:
```

we extend the common subarray that ended just before both positions:

```python
dp[i][j] = dp[i - 1][j - 1] + 1
```

Then we update the best length found so far:

```python
answer = max(answer, dp[i][j])
```

If the values do not match, the DP value stays `0`.

That is correct because a contiguous common subarray cannot end at two different values.

## Space-Optimized Implementation

We only need the previous diagonal value.

Using one row, iterate `j` from right to left so `dp[j - 1]` still refers to the previous row.

```python
class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        m = len(nums1)
        n = len(nums2)

        dp = [0] * (n + 1)
        answer = 0

        for i in range(1, m + 1):
            for j in range(n, 0, -1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[j] = dp[j - 1] + 1
                    answer = max(answer, dp[j])
                else:
                    dp[j] = 0

        return answer
```

## Space-Optimized Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(mn)` | Same number of comparisons |
| Space | `O(n)` | Only one DP row is stored |

## Example Walkthrough

Use:

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

The matching sequence:

```python
[3, 2, 1]
```

appears as:

```python
nums1[2:5]
nums2[0:3]
```

When the DP reaches these matching ending pairs:

| Pair | Match Length |
|---|---:|
| `3` and `3` | `1` |
| `2` and `2` | `2` |
| `1` and `1` | `3` |

So the maximum DP value becomes:

```python
3
```

## Testing

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

    assert s.findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]) == 3
    assert s.findLength([0, 0, 0, 0, 0], [0, 0, 0, 0, 0]) == 5
    assert s.findLength([1, 2, 3], [4, 5, 6]) == 0
    assert s.findLength([1], [1]) == 1
    assert s.findLength([1], [2]) == 0
    assert s.findLength([1, 2, 1, 2, 3], [1, 2, 3, 1, 2]) == 3

    print("all tests passed")

test_find_length()
```

Test coverage:

| Test | Why |
|---|---|
| Standard example | Confirms repeated subarray in the middle |
| All equal values | Confirms full-length match |
| No shared values | Confirms zero result |
| Single equal element | Confirms minimum positive match |
| Single different element | Confirms minimum zero match |
| Repeated patterns | Confirms the algorithm finds the longest contiguous match |