# Maximum Length of Repeated Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-length-of-repeated-subarray)
Canonical: https://scaleengineer.com/dsa/problems/maximum-length-of-repeated-subarray
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
Given two integer arrays `nums1` and `nums2`, return _the maximum length of a subarray that appears in **both** arrays_.

**Example 1:**

**Input:** nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
**Output:** 3
**Explanation:** The repeated subarray with maximum length is [3,2,1].

**Example 2:**

**Input:** nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
**Output:** 5
**Explanation:** The repeated subarray with maximum length is [0,0,0,0,0].

**Constraints:**

* `1 <= nums1.length, nums2.length <= 1000`
* `0 <= nums1[i], nums2[i] <= 100`

# Approaches
## Brute Force
This approach exhaustively checks every possible subarray from the first array (`nums1`) and sees if it exists in the second array (`nums2`). While simple to understand, it's highly inefficient.
**Time:** O(N * M * min(N, M)), where N and M are the lengths of `nums1` and `nums2`. The three nested loops lead to this complexity. For each pair of starting points (i, j), we might iterate up to `min(N, M)` times. · **Space:** O(1), as we only use a few variables to store indices and the maximum length.
**Pros:** Simple to conceive and implement.; Very low memory usage.
**Cons:** Extremely slow for large inputs, likely to result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We use three nested loops. The first two loops define all possible starting points `i` in `nums1` and `j` in `nums2`. The third loop (or a `while` loop) then checks for the length of the common subarray starting at these points. We iterate through all pairs of starting indices `(i, j)` from `nums1` and `nums2`. For each pair, we count how many consecutive elements are identical (`nums1[i+k] == nums2[j+k]`). We keep track of the maximum count found across all pairs.

```java
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int maxLength = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int k = 0;
                while (i + k < nums1.length && j + k < nums2.length && nums1[i + k] == nums2[j + k]) {
                    k++;
                }
                maxLength = Math.max(maxLength, k);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Iterate through `nums1` with index `i` from `0` to `nums1.length - 1`.
- Inside this loop, iterate through `nums2` with index `j` from `0` to `nums2.length - 1`.
- If `nums1[i] == nums2[j]`, it marks a potential start of a common subarray.
- Start a third loop with index `k` to find the length of this common subarray.
- While `i + k < nums1.length`, `j + k < nums2.length`, and `nums1[i + k] == nums2[j + k]`, increment `k`.
- After the inner loop, `k` is the length of the common subarray starting at `(i, j)`. Update `maxLength = max(maxLength, k)`.
- After all loops complete, return `maxLength`.

## Dynamic Programming
A more efficient approach using dynamic programming to avoid re-computation. We build a 2D table to store the lengths of common subarrays.
**Time:** O(N * M), as we iterate through each cell of the `(N+1) x (M+1)` DP table once. · **Space:** O(N * M) for the 2D DP table.
**Pros:** Much faster than the brute-force approach.; Guaranteed to find the correct solution.
**Cons:** High space complexity, which can be an issue for very large arrays.
### Explanation
We define a 2D DP table, `dp[i][j]`, to represent the length of the longest common subarray that *ends* at `nums1[i-1]` and `nums2[j-1]`. The state transition is as follows:
- If `nums1[i-1]` is equal to `nums2[j-1]`, it means we can extend the common subarray that ended at `nums1[i-2]` and `nums2[j-2]`. Therefore, `dp[i][j] = dp[i-1][j-1] + 1`.
- If `nums1[i-1]` is not equal to `nums2[j-1]`, the common subarray streak is broken, so `dp[i][j] = 0`.
The maximum value found anywhere in the `dp` table during the computation will be our answer. We need a separate variable to track this maximum, as the longest common subarray can end at any position.

```java
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];
        int maxLength = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Let N and M be the lengths of `nums1` and `nums2`.
- Create a 2D array `dp` of size `(N+1) x (M+1)` and initialize all its elements to 0.
- Initialize a variable `maxLength = 0`.
- Iterate with `i` from 1 to N.
- Inside, iterate with `j` from 1 to M.
- Check if `nums1[i-1] == nums2[j-1]`.
- If they are equal, set `dp[i][j] = dp[i-1][j-1] + 1`.
- Update `maxLength = max(maxLength, dp[i][j])`.
- If they are not equal, `dp[i][j]` remains 0 (by initialization).
- After the loops, return `maxLength`.

## Space-Optimized Dynamic Programming
This approach improves upon the standard DP solution by reducing its space complexity. It recognizes that to compute the current row of the DP table, we only need the information from the previous row.
**Time:** O(N * M), same as the standard DP approach. · **Space:** O(min(N, M)), a significant improvement over the standard DP approach.
**Pros:** Efficient in both time and space for typical constraints.; Significant space improvement over the standard DP approach.
**Cons:** Still has a quadratic time complexity, which might be too slow if N and M are very large (e.g., > 10^4).
### Explanation
Instead of a 2D `dp` table, we can use a 1D array, say `dp` of size `M+1` (where M is the length of the smaller array). `dp[j]` will store the length of the common subarray ending at `nums2[j-1]` for the current row `i` of `nums1`.
When we compute the values for row `i` (corresponding to `nums1[i-1]`), the new `dp[j]` depends on the old `dp[j-1]` (from row `i-1`). If we iterate `j` from left to right, we would overwrite `dp[j-1]` before it's used to calculate `dp[j]`. To solve this, we iterate the inner loop for `j` backwards (from `M` down to 1). This way, when we calculate `dp[j]`, the value `dp[j-1]` still holds the result from the previous row `i-1`.

```java
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        // Ensure nums2 is the shorter array to optimize space
        if (n < m) {
            return findLength(nums2, nums1);
        }
        
        int[] dp = new int[m + 1];
        int maxLength = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    maxLength = Math.max(maxLength, dp[j]);
                } else {
                    dp[j] = 0;
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Let N and M be the lengths of `nums1` and `nums2`. To optimize, ensure M <= N (swap arrays if not).
- Create a 1D array `dp` of size `M+1` and initialize to 0.
- Initialize `maxLength = 0`.
- Iterate with `i` from 1 to N.
- Inside, iterate with `j` from M down to 1.
- If `nums1[i-1] == nums2[j-1]`:
    - `dp[j] = dp[j-1] + 1`.
    - `maxLength = max(maxLength, dp[j])`.
- Else:
    - `dp[j] = 0` (to reset the count for non-matching elements).
- After the loops, return `maxLength`.

## Binary Search on Length with Hashing
The most efficient approach, which combines binary search on the answer with a rolling hash technique (Rabin-Karp) to quickly check for the existence of common subarrays of a given length.
**Time:** O((N + M) * log(min(N, M))). The binary search takes `log(min(N, M))` steps. In each step, the `check` function with rolling hash takes O(N + M) time. · **Space:** O(min(N, M)) to store the hashes of the subarrays of the smaller array.
**Pros:** Asymptotically the fastest solution.; Very efficient for large inputs.
**Cons:** More complex to implement correctly.; Relies on hashing, which has a theoretical (though extremely small) chance of collision, which could lead to a wrong answer if not handled by secondary verification.
### Explanation
The problem has a monotonic property: if a common subarray of length `k` exists, then a common subarray of any length less than `k` also exists. This allows us to binary search for the maximum possible length `L` in the range `[0, min(N, M)]`.
For each `mid` length in our binary search, we need a `check(mid)` function to verify if a common subarray of length `mid` exists. We can do this efficiently using a rolling hash.
1.  **`check(length)` function:**
    -   Calculate the rolling hashes of all subarrays of `nums1` of the given `length`. Store these hashes in a `HashSet`. This takes O(N) time.
    -   Calculate the rolling hashes of all subarrays of `nums2` of the given `length`. For each hash, check if it exists in the `HashSet` created from `nums1`. If a match is found, we return `true`. This takes O(M) time.
    -   If no match is found after checking all subarrays of `nums2`, return `false`.
2.  **Binary Search:**
    -   If `check(mid)` returns `true`, it means a length of `mid` is possible, so we try for a larger length (`low = mid + 1`).
    -   If `check(mid)` returns `false`, `mid` is too long, so we must try a smaller length (`high = mid`).

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int low = 0, high = Math.min(n, m) + 1;
        int ans = 0;

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                low = 1;
                continue;
            }
            if (check(mid, nums1, nums2)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return ans;
    }

    private boolean check(int length, int[] nums1, int[] nums2) {
        long base = 101; // A prime base
        long modulus = 1_000_000_007; // A large prime modulus
        
        long power = 1;
        for (int i = 0; i < length - 1; i++) {
            power = (power * base) % modulus;
        }

        Set<Long> hashes = new HashSet<>();
        long currentHash = 0;

        // Calculate hashes for nums1
        for (int i = 0; i < nums1.length; i++) {
            if (i < length) {
                currentHash = (currentHash * base + nums1[i]) % modulus;
                if (i == length - 1) {
                    hashes.add(currentHash);
                }
            } else {
                long prevVal = nums1[i - length];
                currentHash = (currentHash - prevVal * power) % modulus;
                if (currentHash < 0) currentHash += modulus; // Ensure positive
                currentHash = (currentHash * base + nums1[i]) % modulus;
                hashes.add(currentHash);
            }
        }

        // Check for matching hash in nums2
        currentHash = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (i < length) {
                currentHash = (currentHash * base + nums2[i]) % modulus;
                if (i == length - 1) {
                    if (hashes.contains(currentHash)) return true;
                }
            } else {
                long prevVal = nums2[i - length];
                currentHash = (currentHash - prevVal * power) % modulus;
                if (currentHash < 0) currentHash += modulus;
                currentHash = (currentHash * base + nums2[i]) % modulus;
                if (hashes.contains(currentHash)) return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Define a search range `low = 1`, `high = min(N, M) + 1`.
- `ans = 0`.
- While `low < high`:
    - `mid = low + (high - low) / 2`.
    - If `check(mid)` is true: `ans = mid`, `low = mid + 1`.
    - Else: `high = mid`.
- Return `ans`.
- The `check(length)` function uses rolling hash. It computes hashes for all subarrays of `length` in `nums1` and stores them in a set. Then, it computes hashes for subarrays in `nums2` and checks for a match in the set.

# Solutions
### Java

```java
class Solution {
public
  int findLength(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int[][] f = new int[m + 1][n + 1];
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (nums1[i - 1] == nums2[j - 1]) {
          f[i][j] = f[i - 1][j - 1] + 1;
          ans = Math.max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findLength =
  function (nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const f = Array.from({ length: m + 1 }, (_) => new Array(n + 1).fill(0));
    let ans = 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;
          ans = Math.max(ans, f[i][j]);
        }
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int findLength(vector<int> &nums1, vector<int> &nums2) {
    int m = nums1.size(), n = nums2.size();
    vector<vector<int>> f(m + 1, vector<int>(n + 1));
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (nums1[i - 1] == nums2[j - 1]) {
          f[i][j] = f[i - 1][j - 1] + 1;
          ans = max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
''' # only set(), not list() >>> nums1 = [1,2,3,2,1] >>> nums2 = [3,2,1,4,7] >>> nums1 & nums2 Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unsupported operand type(s) for &: 'list' and 'list' ''' class Solution : def findLength ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : m , n = len ( nums1 ), len ( nums2 ) dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] ans = 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 ] = 1 + dp [ i - 1 ][ j - 1 ] ans = max ( ans , dp [ i ][ j ]) return ans ############ class Solution : # also OJ passed, with j iterated reversely def findLength ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : m , n = len ( nums1 ), len ( nums2 ) dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] ans = 0 for i in range ( 1 , m + 1 ): for j in range ( n , 0 , - 1 ): if nums1 [ i - 1 ] == nums2 [ j - 1 ]: dp [ i ][ j ] = 1 + dp [ i - 1 ][ j - 1 ] ans = max ( ans , dp [ i ][ j ]) return ans ############ class Solution : def findLength ( self , A , B ): """ :type A: List[int] :type B: List[int] :rtype: int """ m , n = len ( A ), len ( B ) dp = [[ 0 for j in range ( n + 1 )] for i in range ( m + 1 )] max_len = 0 for i in range ( m + 1 ): for j in range ( n + 1 ): if i == 0 or j == 0 : dp [ i ][ j ] = 0 elif A [ i - 1 ] == B [ j - 1 ]: dp [ i ][ j ] = dp [ i - 1 ][ j - 1 ] + 1 max_len = max ( max_len , dp [ i ][ j ]) return max_len
```