# 718. Maximum Length of Repeated Subarray

## Description

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

## Solutions

Use dynamic programming. Create a 2D array dp of A.length + 1 rows and B.length + 1 columns, where dp[i][j] represents the maximum length of repeated subarray of the two subarray A[i..] and B[j..].

Initially, all elements in dp are 0. For i from A.length - 1 to 0 and j from B.length - 1 to 0, if A[i] == B[j], then there is a repeated subarray that starts from index i in A and index j in B, so update dp[i][j] = dp[i + 1][j + 1] + 1, and update the maximum length of a repeated subarray. Finally, return the maximum length of a repeated subarray.

• 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;
}
}

• 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;
}
};

• '''
# 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


• func findLength(nums1 []int, nums2 []int) (ans int) {
m, n := len(nums1), len(nums2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
f[i][j] = f[i-1][j-1] + 1
if ans < f[i][j] {
ans = f[i][j]
}
}
}
}
return ans
}

• function findLength(nums1: number[], nums2: number[]): number {
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;
}


• /**
* @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;
};