Maximum Length of Repeated Subarray | Problems

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays. A subarray is a contiguous part of an array.

Example:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3 (subarray [3,2,1])

Sample Input

—

Sample Output

—

Constraints

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

Test Cases

Case 1

Args: [[1,2,3,2,1],[3,2,1,4,7]] Expected: 3

Topics

Dynamic Programming Memoization

Approach: Dynamic Programming

dp[i][j] stores the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]. If the values match, dp[i][j] = dp[i-1][j-1] + 1. Track the maximum.

function maximumLengthOfRepeatedSubarray(nums1, nums2) {
  const m = nums1.length, n = nums2.length;
  const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
  let max = 0;
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      if (nums1[i-1] === nums2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
        max = Math.max(max, dp[i][j]);
      }
  return max;
}

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Saved in this browser only. Private to you.