# Solution For Maximum Length Of Repeated Subarray

Problem Statement:

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

Solution:

Approach:
The brute-force solution for this problem is to check every possible subarray in the two given arrays to find if they have any common subarray and then return the maximum length. However, this would take O(n^3) time complexity, which is not optimal for large inputs and would exceed the time limit.

To optimize the solution, we can use dynamic programming. We can maintain a 2D array, dp, where dp[i][j] represents the length of the longest common subarray if the subarrays start at i in nums1 and j in nums2. The length of the longest common subarray would be the maximum element of the dp matrix and can be returned as the answer.

Let’s break down the approach into steps:

• Initialize a 2D dp array of size (n+1)x(m+1) where n and m are the lengths of nums1 and nums2 respectively. We add 1 to the sizes because we want to handle the case where one of the arrays is empty.
• Set all the elements of the first row and first column of the dp array to 0 since there would be no common subarrays between an empty array and any other subarray.
• Loop through the dp array from i=1 to n and j=1 to m. If nums1[i-1] and nums2[j-1] are equal, then we update dp[i][j] by adding 1 to dp[i-1][j-1], since we have found a common element. If they are not equal, then we set dp[i][j]=0 because there is no common subarray that ends with nums1[i-1] and nums2[j-1].
• While updating dp, we keep track of the maximum element we encounter, which gives us the length of the longest common subarray.
• Finally, we return the maximum element of the dp array.

Time Complexity:
The time complexity of this solution is O(n*m), where n and m are the lengths of the input arrays.

Python Code:

class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
n, m = len(nums1), len(nums2)
dp = [*(m+1) for _ in range(n+1)]

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

return max_len
``````

Java Code:

class Solution {
public int findLength(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
int[][] dp = new int[n+1][m+1];
int max_len = 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;
max_len = Math.max(max_len, dp[i][j]);
}
}
}

return max_len;
}
``````

}

## Step by Step Implementation For Maximum Length Of Repeated Subarray

```class Solution {
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int[][] dp = new int[n+1][m+1];
int max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max;
}
}```
```class Solution:
def findLength(self, A: List[int], B: List[int]) -> int:
# create a 2D array to store the length of the longest common subarray
# for each pair of indices
dp = [[0 for _ in range(len(B)+1)] for _ in range(len(A)+1)]

# iterate through each row
for i in range(len(A)):
# iterate through each column
for j in range(len(B)):
# if the current elements in each array match,
# increment the value in the dp array
if A[i] == B[j]:
dp[i+1][j+1] = dp[i][j] + 1

# return the maximum value in the dp array
return max(map(max, dp))```
```/**
* @param {number[]} A
* @param {number[]} B
* @return {number}
*/
var findLength = function(A, B) {
// dp[i][j] is the length of the longest common subarray ending at index i in A and index j in B
let dp = new Array(A.length + 1);
for (let i = 0; i <= A.length; i++) {
dp[i] = new Array(B.length + 1).fill(0);
}

let maxLength = 0;
for (let i = 1; i <= A.length; i++) {
for (let j = 1; j <= B.length; j++) {
if (A[i - 1] === B[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}

return maxLength;
};```
```class Solution {
public:
int findLength(vector& A, vector& B) {
int n = A.size(), m = B.size();
int dp[n+1][m+1];
memset(dp, 0, sizeof dp);
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i-1] == B[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
ans = max(ans, dp[i][j]);
}
}
}
return ans;
}
};```
```public class Solution {
public int FindLength(int[] A, int[] B) {
// dp[i, j] represents the length of the longest common
// subarray ending with the ith element in A and the
// jth element in B
int[,] dp = new int[A.Length, B.Length];
int result = 0;

for (int i = 0; i < A.Length; i++) {
for (int j = 0; j < B.Length; j++) {
if (A[i] == B[j]) {
// If the current elements are the same,
// the length of the longest common subarray
// is equal to the length of the longest common
// subarray ending with the previous elements in
// A and B plus 1
if (i == 0 || j == 0) {
dp[i, j] = 1;
} else {
dp[i, j] = dp[i - 1, j - 1] + 1;
}

// Update the result if necessary
if (dp[i, j] > result) {
result = dp[i, j];
}
}
}
}

return result;
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]