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

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        m = len(nums2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        max_length = 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_length = max(max_length, dp[i][j])
                else:
                    dp[i][j] = 0

        return max_length

Brute Force Solution

A naive approach would be to generate all possible subarrays for both arrays and compare them to find the longest common subarray. This approach has a high time complexity.

def findLength_brute_force(nums1: List[int], nums2: List[int]) -> int:
    max_length = 0
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            length = 0
            while i + length < len(nums1) and j + length < len(nums2) and nums1[i + length] == nums2[j + length]:
                length += 1
            max_length = max(max_length, length)
    return max_length

Optimal Solution

The optimal solution uses dynamic programming to efficiently find the maximum length of a subarray that appears in both arrays.

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        m = len(nums2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        max_length = 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_length = max(max_length, dp[i][j])
                else:
                    dp[i][j] = 0

        return max_length

Big(O) Run-time Analysis

The time complexity of the dynamic programming solution is O(n*m), where n and m are the lengths of nums1 and nums2 respectively. This is because we iterate through each cell of the dp table once, which has dimensions (n+1) x (m+1).

Big(O) Space Usage Analysis

The space complexity of the dynamic programming solution is O(n*m) because we use a 2D array dp of size (n+1) x (m+1) to store the lengths of common subarrays.

Edge Cases

1. Empty Arrays: If either nums1 or nums2 is empty, the maximum length of the common subarray is 0.
2. No Common Subarray: If there is no common subarray between nums1 and nums2, the maximum length is 0.
3. Identical Arrays: If nums1 and nums2 are identical, the maximum length is the length of either array.
4. Arrays with Overlapping Elements: The algorithm correctly handles cases where the arrays have overlapping elements, finding the longest common subarray even if it's not contiguous in the original arrays.