Maximum Length of Repeated Subarray

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

For example: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] should return 3 because the longest common subarray is [3,2,1]. nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] should return 5 because the longest common subarray is [0,0,0,0,0].

Consider the time and space complexity of your approach. Can you come up with an optimal solution to solve this problem?

# Maximum Length of Repeated Subarray

## Problem Description

Given two integer arrays `nums1` and `nums2`, the goal is to find 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].

## Brute Force Solution

A naive approach involves comparing all possible subarrays of `nums1` with all possible subarrays of `nums2`. This approach has a high time complexity but is straightforward to understand.

```python
def findLength_brute_force(nums1, nums2):
    max_len = 0
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            k = 0
            while i + k < len(nums1) and j + k < len(nums2) and nums1[i + k] == nums2[j + k]:
                k += 1
            max_len = max(max_len, k)
    return max_len

Optimal Solution: Dynamic Programming

A more efficient solution uses dynamic programming. We create a 2D array dp where dp[i][j] stores the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]. The value of dp[i][j] is updated based on whether nums1[i-1] and nums2[j-1] are equal.

def findLength(nums1, nums2):
    n = len(nums1)
    m = 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])
            else:
                dp[i][j] = 0
                
    return max_len

Big(O) Time Complexity Analysis

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

Big(O) Space Complexity Analysis

The space complexity is also 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 function should return 0.
3. Identical Arrays: If nums1 and nums2 are identical, the maximum length is the length of either array.
4. Arrays with Duplicate Elements: The algorithm should correctly handle arrays with duplicate elements and find the longest common subarray regardless of the duplicates.

These edge cases are handled correctly by both the brute force and dynamic programming solutions.