718. Maximum Length of Repeated Subarray
mediumFind the longest contiguous subarray that appears in both arrays. Subtle twist on LCS — contiguity means we reset on mismatch instead of carrying max.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Constraints
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
Examples
Example 1
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]3Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2
nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]5Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Subarray means contiguous — different from subsequence.
Hint 2
dp[i][j] = length of common subarray ending at nums1[i-1] and nums2[j-1].
Hint 3
On match: dp[i][j] = dp[i-1][j-1] + 1. On mismatch: dp[i][j] = 0. Track a running max.
Solution approach
Reveal approach
Define the subproblem dp[i][j] = the length of the longest common subarray that ends exactly at nums1[i-1] and nums2[j-1]. The recurrence relation is dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1], else dp[i][j] = 0 — the mismatch resets the chain because subarrays must be contiguous. Base cases dp[0][j] = dp[i][0] = 0. Maintain a running max as you fill the table; the answer is that max, not dp[m][n]. This is the structural difference from LCS (which carries forward through mismatches via max(dp[i-1][j], dp[i][j-1])). Time O(m * n), space O(m * n); reduce to O(min(m, n)) with rolling rows or two 1D arrays.
Complexity
- Time
- O(m * n)
- Space
- O(m * n)
Related patterns
- dynamic-programming
- memoization-recursion
- string-dp
Related problems
- 1143. Longest Common Subsequence
- 72. Edit Distance
- 53. Maximum Subarray
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
Practice these live with InterviewChamp.AI
Drill Maximum Length of Repeated Subarray and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →