##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/718.html

# 718. Maximum Length of Repeated Subarray

Medium

## Description

Given two integer arrays A and B, return the maximum length of a subarray that appears in both arrays.

Example 1:

Input:

A: [1,2,3,2,1]

B: [3,2,1,4,7]

Output: 3

Explanation:

The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

## Solution

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.

• public class Maximum_Length_of_Repeated_Subarray {

// time: O(M*N)
// space: O(M*N)
class Solution {
public int findLength(int[] A, int[] B) {
int ans = 0;

// dp[i][j] be the longest common prefix of A[i:] and B[j:].
// Whenever A[i] == B[j], we know dp[i][j] = dp[i+1][j+1] + 1.
// Also, the answer is max(dp[i][j]) over all i, j
int[][] memo = new int[A.length + 1][B.length + 1];

for (int i = A.length - 1; i >= 0; --i) {
for (int j = B.length - 1; j >= 0; --j) {
if (A[i] == B[j]) {
memo[i][j] = memo[i+1][j+1] + 1;
if (ans < memo[i][j]) ans = memo[i][j];
}
}
}
return ans;
}
}

class Solution_overTime {

int max = 0;

public int findLength(int[] A, int[] B) {

if (A == null || B == null || A.length == 0 || B.length == 0) {
return 0;
}

for (int i = 0; i < A.length; i++) {
int c = A[i];

// look for possible match in array B
for (int j = 0; j < B.length; j++) {
if (B[j] == c) {
checkSubLength(A, B, i, j);
}
}
}

return max;
}

private void checkSubLength(int[] A, int[] B, int i, int j) {

int count = 0;

while (i < A.length && j < B.length && A[i++] == B[j++]) {
count++;
}
this.max = Math.max(this.max, count);
}

}
}

class Solution {
public int findLength(int[] A, int[] B) {
int maxLength = 0;
int length1 = A.length, length2 = B.length;
int[][] dp = new int[length1 + 1][length2 + 1];
for (int i = length1 - 1; i >= 0; i--) {
for (int j = length2 - 1; j >= 0; j--) {
if (A[i] == B[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
}

############

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

• // OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// Time: O(MN)
// Space: O(min(M, N))
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
if (A.size() < B.size()) swap(A, B);
int M = A.size(), N = B.size(), ans = 0;
vector<int> dp(N + 1, 0);
for (int i = 0; i < M; ++i) {
for (int j = N - 1; j >= 0; --j) {
dp[j + 1] = A[i] == B[j] ? 1 + dp[j] : 0;
ans = max(ans, dp[j + 1]);
}
}
return ans;
}
};

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