Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5 Explanation: The repeated subarray with maximum length is [0,0,0,0,0].
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100Problem Overview: Given two integer arrays, find the length of the longest subarray that appears in both arrays. The subarray must be contiguous in both arrays, which makes the problem closer to longest common substring rather than the classic longest common subsequence.
Approach 1: Dynamic Programming (O(n * m) time, O(n * m) space)
This approach treats the problem exactly like the Longest Common Substring. Create a 2D DP table where dp[i][j] stores the length of the longest matching suffix ending at nums1[i-1] and nums2[j-1]. If the elements match, extend the previous match with dp[i][j] = dp[i-1][j-1] + 1. If they differ, reset the value to 0 because the subarray must remain contiguous. Track the maximum value while filling the table. This solution is straightforward and reliable, making it ideal for interviews when discussing dynamic programming. You can reduce memory to O(min(n, m)) by keeping only the previous row.
Approach 2: Binary Search + Rolling Hash (O((n + m) log(min(n,m))) time, O(n) space)
A faster approach combines binary search with a rolling hash. Instead of checking every possible subarray length directly, binary search the answer. For a candidate length k, compute rolling hashes for all subarrays of length k in the first array and store them in a hash set. Then slide a window of length k across the second array and check whether any hash matches. Matching hashes indicate a potential repeated subarray. If a match exists, increase the search range; otherwise decrease it. Rolling hash lets you update each window in constant time, which keeps the check efficient even for large arrays.
This hashing approach scales better when arrays grow large because it avoids filling an n × m table. It also demonstrates practical use of sliding window techniques with hashing to compare subarrays efficiently.
Recommended for interviews: Start with the dynamic programming formulation. It clearly models the contiguous constraint and shows strong understanding of DP patterns. After that, discuss the binary search + rolling hash optimization. Interviewers often value candidates who recognize the longest-common-substring relationship first, then propose hashing to reduce runtime for larger inputs.
This approach uses a 2D DP array where dp[i][j] represents the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]. Initialize the DP table with zeros. If nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1, otherwise set it to 0. Track the maximum length found throughout the process.
This solution constructs a 2D array for maintaining the lengths of common subarrays at each ending position for both arrays. When matching elements are found, it extends the length from the previous subarray and potentially updates the maximum length found.
Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2, respectively. Space Complexity: O(n * m) due to the DP table.
This approach involves using a sliding window over the two arrays with the help of a hashing method to check potential matches of subarrays. By varying the window size, you can find the length of the longest matching subarray without needing a full DP table.
The C solution selectively shifts and iterates over subarrays, checking integer matches directly as the two pointers overlap, recalculating lengths and ensuring a memory-efficient solution.
Time Complexity: O(n * m), Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2, respectively. Space Complexity: O(n * m) due to the DP table. |
| Sliding Window with Hashing | Time Complexity: O(n * m), Space Complexity: O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n * m) | O(n * m) (or O(min(n,m)) optimized) | Best for clarity and interviews when arrays are moderate in size |
| Binary Search + Rolling Hash | O((n + m) log(min(n,m))) | O(n) | Better for large arrays where DP table becomes expensive |
Maximum Length of Repeated Subarray | Dynamic Programming | Leetcode 718 • Pepcoding • 13,487 views views
Watch 9 more video solutions →Practice Maximum Length of Repeated Subarray with our built-in code editor and test cases.
Practice on FleetCode