Maximum Length of Repeated Subarray

The key idea

A repeated subarray must be contiguous, so let dp[i][j] be the length of the common run that ENDS exactly at nums1[i-1] and nums2[j-1]. When the two elements match, the run extends the diagonal: dp[i][j] = dp[i-1][j-1] + 1. A mismatch breaks the run, so the cell is 0. The answer is the largest value anywhere in the table.

Problem

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

A subarray is a contiguous sequence of elements within an array. The two matching subarrays must line up element-for-element with no gaps, but they may start at different positions in nums1 and nums2.

Constraints

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

Examples

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

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5

Complexity

Time: O(n*m) Space: O(n*m)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →