Maximum Length Of Repeated Subarray - Leetcode Solution

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 = [[0]*(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;
}

}

1