Maximum Length of Repeated Subarray Medium 0 attempts
LeetCode ↗

Maximum Length of Repeated Subarray

Medium Dynamic ProgrammingMemoization LeetCode

You're given two integer arrays, nums1 and nums2. Find the length of the longest contiguous run of elements that shows up identically in both arrays, in the same order.

Input Format
Implement maximumLengthOfRepeatedSubarray(nums1, nums2). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
nums1 = [1,2,3,2,1]
nums2 = [3,2,1,4,7]
Output
3

Example 2

Input
nums1 = [0,0]
nums2 = [0]
Output
1
Constraints
  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100
Test Cases (2)
Case 1
Args: [[1,2,3,2,1],[3,2,1,4,7]] Expected: 3
Case 2
Args: [[0,0],[0]] Expected: 1
Topics
Dynamic ProgrammingMemoization

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.

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

JavaScript