algoadvance

You are given two integer arrays nums1 and nums2. You need to return the maximum length of a subarray that appears in both arrays.

Example:

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].

Clarifying Questions

  1. What is the length of the arrays?
    • The lengths of the arrays can be up to 1000 elements.
  2. Are the arrays always non-empty?
    • Yes, you can assume that nums1 and nums2 will always have at least one element.
  3. Can the elements be negative or non-integer?
    • The elements will always be integers and could be negative as well.

Strategy

The problem of finding the maximum length of a subarray that appears in both arrays can be efficiently solved using dynamic programming (DP).

Dynamic Programming Approach:

  1. Create a DP table:
    • Let dp[i][j] represent the length of the longest common subarray ending at nums1[i-1] and nums2[j-1].
    • A table dp of size (len(nums1) + 1) x (len(nums2) + 1) will be used where dp[0][*] and dp[*][0] are initialized to 0.
  2. Update the DP table:
    • For each pair (i, j), if nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
    • Otherwise, set dp[i][j] = 0 because the subarrays ending at those points do not match.
  3. Track the maximum length:
    • During the process, keep track of the maximum value found in dp[i][j].

Time Complexity

Code

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 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

# Example usage:
nums1 = [1, 2, 3, 2, 1]
nums2 = [3, 2, 1, 4, 7]
print(findLength(nums1, nums2))  # Output: 3

This solution fills out the DP table based on the rules and efficiently keeps track of the maximum length of the repeated subarray.

Try our interview co-pilot at AlgoAdvance.com