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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Length of Repeated Subarray

Difficulty: Medium

Problem Description

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

Key Insights

  • A subarray is a contiguous part of an array.
  • The problem requires finding the longest common contiguous subarray between two arrays.
  • Dynamic Programming is an effective approach to solve this problem, where we can build a table to store lengths of common subarrays.

Space and Time Complexity

Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2, respectively.
Space Complexity: O(n * m) for the DP table.

Solution

To solve this problem, we can use a Dynamic Programming approach. We will create a 2D array (or table) where each entry dp[i][j] represents the length of the longest common subarray ending at nums1[i-1] and nums2[j-1].

  1. Initialize a 2D array dp with dimensions (n+1) x (m+1) to zero, where n is the length of nums1 and m is the length of nums2.
  2. Iterate through both arrays. If nums1[i-1] is equal to nums2[j-1], then update dp[i][j] as dp[i-1][j-1] + 1.
  3. Keep track of the maximum length found during these updates.
  4. The final answer will be the maximum value found in the dp table.

Code Solutions

def findLength(nums1, nums2):
    n, m = len(nums1), 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])
    
    return max_length
← Back to All Questions