{x}
blog image

Maximum Length of Repeated Subarray

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

Solution Explanation:

This problem asks for the maximum length of a subarray that is common to both input arrays nums1 and nums2. A dynamic programming approach is highly efficient for this.

Approach:

We create a 2D array f of size (m+1) x (n+1), where 'm' and 'n' are the lengths of nums1 and nums2 respectively. f[i][j] will store the length of the longest common subarray ending at index i-1 in nums1 and j-1 in nums2.

  • Initialization: The first row and column of f are initialized to 0 because there's no common subarray if one of the arrays is empty.

  • Iteration: We iterate through the f array. If nums1[i-1] and nums2[j-1] are equal, it means we've found an extension of a common subarray. In this case, f[i][j] becomes f[i-1][j-1] + 1. Otherwise, f[i][j] remains 0.

  • Maximum Length: Throughout the iteration, we keep track of the maximum value encountered in f, which represents the maximum length of the common subarray.

Time Complexity: O(m*n), where 'm' and 'n' are the lengths of the input arrays. This is because we iterate through the entire 2D array f.

Space Complexity: O(m*n), due to the space used by the f array. It's possible to optimize this to O(min(m,n)) by using only two rows (or columns) of the DP array, but the provided solution prioritizes clarity.

Code Explanation (Python3):

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        f = [[0] * (n + 1) for _ in range(m + 1)] # Initialize DP array
        ans = 0 # Initialize maximum length
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i - 1] == nums2[j - 1]: # Check for match
                    f[i][j] = f[i - 1][j - 1] + 1 # Extend common subarray length
                    ans = max(ans, f[i][j]) # Update maximum length
        return ans

The Python code directly implements the dynamic programming approach described above. The nested loops iterate through the f array, updating the lengths of common subarrays and tracking the maximum length.

The other languages (Java, C++, Go, TypeScript, JavaScript) follow the same logic and algorithm, only differing in syntax and specific data structure implementations. They all have the same time and space complexity.