We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Length of Repeated Subarray

Number: 718

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, Amazon, Microsoft, Citadel

Problem Description

Given two integer arrays, find the maximum length of a subarray that appears in both arrays.

Key Insights

  • Use Dynamic Programming to compare subarrays ending at different indices.
  • Create a 2D dp array where dp[i][j] represents the length of the longest common subarray ending at nums1[i-1] and nums2[j-1].
  • Update dp[i][j] as dp[i-1][j-1] + 1 when corresponding elements match.
  • Track the maximum value in dp during iteration.
  • The overall approach has a time complexity of O(n*m) which is acceptable given the constraints.

Space and Time Complexity

Time Complexity: O(nm), where n and m are the lengths of the two input arrays. Space Complexity: O(nm) for the dp array used to store intermediate results.

Solution

We solve this problem using Dynamic Programming. We construct a 2D dp matrix where each cell dp[i][j] represents the length of the longest common subarray ending at index i-1 in the first array and j-1 in the second array. When the elements at these positions match, we update dp[i][j] to be 1 plus the value from the previous indices (dp[i-1][j-1]). We keep a global variable to track the maximum length found during the iterations. Finally, we return this maximum length.

Code Solutions

def findLength(nums1, nums2):
    # Determine the lengths of the input arrays
    m, n = len(nums1), len(nums2)
    # Create a dp matrix with dimensions (m+1) x (n+1) initialized to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # Variable to store the maximum subarray length found
    max_length = 0
    # Iterate over the arrays starting from 1 since dp is 1-indexed
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If elements match, update dp table accordingly
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_length = max(max_length, dp[i][j])
    return max_length

# Example usage:
print(findLength([1,2,3,2,1], [3,2,1,4,7]))  # Output: 3
← Back to All Questions