Maximum Length of Repeated Subarray - Solution & Explanation
Problem Statement
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] <= 100
Approach Overview
Problem 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.
Approach 1: Dynamic Programming
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.
Complexity
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.
Approach 2: Sliding Window with Hashing
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.
Complexity
Time Complexity: O(n * m), Space Complexity: O(1).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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). |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Length of Repeated Subarray | Dynamic Programming | Leetcode 718 • Pepcoding • 13,580 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Length of Repeated Subarray easy or hard?
Maximum Length of Repeated Subarray Python/Java solution
How to solve Maximum Length of Repeated Subarray in O(n)?
What is the best approach for Maximum Length of Repeated Subarray?
Is Maximum Length of Repeated Subarray asked at Google/Amazon/Meta?
What data structure is used in Maximum Length of Repeated Subarray?
What is the time complexity of Maximum Length of Repeated Subarray?
Ready to solve this problem?
Practice Maximum Length of Repeated Subarray with our built-in code editor and test cases.
Practice on FleetCode