476. Maximum Length of Repeated Subarray
You are given two integer arrays nums1 and nums2. A subarray is a contiguous run of elements — order matters and no gaps are allowed.
Return the length of the longest run of consecutive elements that shows up in both arrays. If the arrays share no common element, the answer is 0.
Note this is not longest common subsequence: [1, 2, 3] and [1, 9, 2, 9, 3] share the subsequence 1, 2, 3 but their longest common subarray has length 1.
Example 1:
Input: nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]
Output: 3
Explanation: The run [3, 2, 1] occupies nums1[2..4] and nums2[0..2] — three elements, contiguous in both.
Example 2:
Input: nums1 = [0, 0, 0, 0, 1], nums2 = [1, 0, 0, 0, 0]
Output: 4
Explanation: Four zeros in a row appear in both: nums1[0..3] and nums2[1..4]. The full arrays differ, so 5 is impossible.
Constraints:
- 1 ≤ nums1.length, nums2.length ≤ 1000
- 0 ≤ nums1[i], nums2[i] ≤ 100
Hints:
Every common run ends somewhere: at some pair of positions (i, j) with nums1[i] == nums2[j]. Think about the longest common run that ends exactly there.
If dp[i][j] is the length of the longest common run ending at nums1[i] and nums2[j], then a match extends the diagonal neighbor: dp[i][j] = dp[i-1][j-1] + 1, and a mismatch resets it to 0. The answer is the largest cell.
Each dp row only reads the previous row, and only its left neighbor diagonally — one 1-D array updated right-to-left (or two rows) is enough memory.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]
Expected output: 3