Maximum Length of Repeated Subarray
MedPrompt
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
Approaches
4 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible subarray from the first array (nums1) and sees if it exists in the second array (nums2). While simple to understand, it's highly inefficient.
Algorithm
- Initialize
maxLength = 0. - Iterate through
nums1with indexifrom0tonums1.length - 1. - Inside this loop, iterate through
nums2with indexjfrom0tonums2.length - 1. - If
nums1[i] == nums2[j], it marks a potential start of a common subarray. - Start a third loop with index
kto find the length of this common subarray. - While
i + k < nums1.length,j + k < nums2.length, andnums1[i + k] == nums2[j + k], incrementk. - After the inner loop,
kis the length of the common subarray starting at(i, j). UpdatemaxLength = max(maxLength, k). - After all loops complete, return
maxLength.
Walkthrough
We use three nested loops. The first two loops define all possible starting points i in nums1 and j in nums2. The third loop (or a while loop) then checks for the length of the common subarray starting at these points. We iterate through all pairs of starting indices (i, j) from nums1 and nums2. For each pair, we count how many consecutive elements are identical (nums1[i+k] == nums2[j+k]). We keep track of the maximum count found across all pairs.
class Solution { public int findLength(int[] nums1, int[] nums2) { int maxLength = 0; for (int i = 0; i < nums1.length; i++) { for (int j = 0; j < nums2.length; j++) { int k = 0; while (i + k < nums1.length && j + k < nums2.length && nums1[i + k] == nums2[j + k]) { k++; } maxLength = Math.max(maxLength, k); } } return maxLength; }}Complexity
Time
O(N * M * min(N, M)), where N and M are the lengths of `nums1` and `nums2`. The three nested loops lead to this complexity. For each pair of starting points (i, j), we might iterate up to `min(N, M)` times.
Space
O(1), as we only use a few variables to store indices and the maximum length.
Trade-offs
Pros
Simple to conceive and implement.
Very low memory usage.
Cons
Extremely slow for large inputs, likely to result in a 'Time Limit Exceeded' error on most platforms.
A more efficient approach using dynamic programming to avoid re-computation. We build a 2D table to store the lengths of common subarrays.
Algorithm
- Let N and M be the lengths of
nums1andnums2. - Create a 2D array
dpof size(N+1) x (M+1)and initialize all its elements to 0. - Initialize a variable
maxLength = 0. - Iterate with
ifrom 1 to N. - Inside, iterate with
jfrom 1 to M. - Check if
nums1[i-1] == nums2[j-1]. - If they are equal, set
dp[i][j] = dp[i-1][j-1] + 1. - Update
maxLength = max(maxLength, dp[i][j]). - If they are not equal,
dp[i][j]remains 0 (by initialization). - After the loops, return
maxLength.
Walkthrough
We define a 2D DP table, dp[i][j], to represent the length of the longest common subarray that ends at nums1[i-1] and nums2[j-1]. The state transition is as follows:
- If
nums1[i-1]is equal tonums2[j-1], it means we can extend the common subarray that ended atnums1[i-2]andnums2[j-2]. Therefore,dp[i][j] = dp[i-1][j-1] + 1. - If
nums1[i-1]is not equal tonums2[j-1], the common subarray streak is broken, sodp[i][j] = 0. The maximum value found anywhere in thedptable during the computation will be our answer. We need a separate variable to track this maximum, as the longest common subarray can end at any position.
class Solution { public int findLength(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int[][] dp = new int[n + 1][m + 1]; int maxLength = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; maxLength = Math.max(maxLength, dp[i][j]); } } } return maxLength; }}Complexity
Time
O(N * M), as we iterate through each cell of the `(N+1) x (M+1)` DP table once.
Space
O(N * M) for the 2D DP table.
Trade-offs
Pros
Much faster than the brute-force approach.
Guaranteed to find the correct solution.
Cons
High space complexity, which can be an issue for very large arrays.
This approach improves upon the standard DP solution by reducing its space complexity. It recognizes that to compute the current row of the DP table, we only need the information from the previous row.
Algorithm
- Let N and M be the lengths of
nums1andnums2. To optimize, ensure M <= N (swap arrays if not). - Create a 1D array
dpof sizeM+1and initialize to 0. - Initialize
maxLength = 0. - Iterate with
ifrom 1 to N. - Inside, iterate with
jfrom M down to 1. - If
nums1[i-1] == nums2[j-1]:dp[j] = dp[j-1] + 1.maxLength = max(maxLength, dp[j]).
- Else:
dp[j] = 0(to reset the count for non-matching elements).
- After the loops, return
maxLength.
Walkthrough
Instead of a 2D dp table, we can use a 1D array, say dp of size M+1 (where M is the length of the smaller array). dp[j] will store the length of the common subarray ending at nums2[j-1] for the current row i of nums1.
When we compute the values for row i (corresponding to nums1[i-1]), the new dp[j] depends on the old dp[j-1] (from row i-1). If we iterate j from left to right, we would overwrite dp[j-1] before it's used to calculate dp[j]. To solve this, we iterate the inner loop for j backwards (from M down to 1). This way, when we calculate dp[j], the value dp[j-1] still holds the result from the previous row i-1.
class Solution { public int findLength(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; // Ensure nums2 is the shorter array to optimize space if (n < m) { return findLength(nums2, nums1); } int[] dp = new int[m + 1]; int maxLength = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { if (nums1[i - 1] == nums2[j - 1]) { dp[j] = dp[j - 1] + 1; maxLength = Math.max(maxLength, dp[j]); } else { dp[j] = 0; } } } return maxLength; }}Complexity
Time
O(N * M), same as the standard DP approach.
Space
O(min(N, M)), a significant improvement over the standard DP approach.
Trade-offs
Pros
Efficient in both time and space for typical constraints.
Significant space improvement over the standard DP approach.
Cons
Still has a quadratic time complexity, which might be too slow if N and M are very large (e.g., > 10^4).
The most efficient approach, which combines binary search on the answer with a rolling hash technique (Rabin-Karp) to quickly check for the existence of common subarrays of a given length.
Algorithm
- Define a search range
low = 1,high = min(N, M) + 1. ans = 0.- While
low < high:mid = low + (high - low) / 2.- If
check(mid)is true:ans = mid,low = mid + 1. - Else:
high = mid.
- Return
ans. - The
check(length)function uses rolling hash. It computes hashes for all subarrays oflengthinnums1and stores them in a set. Then, it computes hashes for subarrays innums2and checks for a match in the set.
Walkthrough
The problem has a monotonic property: if a common subarray of length k exists, then a common subarray of any length less than k also exists. This allows us to binary search for the maximum possible length L in the range [0, min(N, M)].
For each mid length in our binary search, we need a check(mid) function to verify if a common subarray of length mid exists. We can do this efficiently using a rolling hash.
check(length)function:- Calculate the rolling hashes of all subarrays of
nums1of the givenlength. Store these hashes in aHashSet. This takes O(N) time. - Calculate the rolling hashes of all subarrays of
nums2of the givenlength. For each hash, check if it exists in theHashSetcreated fromnums1. If a match is found, we returntrue. This takes O(M) time. - If no match is found after checking all subarrays of
nums2, returnfalse.
- Calculate the rolling hashes of all subarrays of
- Binary Search:
- If
check(mid)returnstrue, it means a length ofmidis possible, so we try for a larger length (low = mid + 1). - If
check(mid)returnsfalse,midis too long, so we must try a smaller length (high = mid).
- If
import java.util.HashSet;import java.util.Set; class Solution { public int findLength(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int low = 0, high = Math.min(n, m) + 1; int ans = 0; while (low < high) { int mid = low + (high - low) / 2; if (mid == 0) { low = 1; continue; } if (check(mid, nums1, nums2)) { ans = mid; low = mid + 1; } else { high = mid; } } return ans; } private boolean check(int length, int[] nums1, int[] nums2) { long base = 101; // A prime base long modulus = 1_000_000_007; // A large prime modulus long power = 1; for (int i = 0; i < length - 1; i++) { power = (power * base) % modulus; } Set<Long> hashes = new HashSet<>(); long currentHash = 0; // Calculate hashes for nums1 for (int i = 0; i < nums1.length; i++) { if (i < length) { currentHash = (currentHash * base + nums1[i]) % modulus; if (i == length - 1) { hashes.add(currentHash); } } else { long prevVal = nums1[i - length]; currentHash = (currentHash - prevVal * power) % modulus; if (currentHash < 0) currentHash += modulus; // Ensure positive currentHash = (currentHash * base + nums1[i]) % modulus; hashes.add(currentHash); } } // Check for matching hash in nums2 currentHash = 0; for (int i = 0; i < nums2.length; i++) { if (i < length) { currentHash = (currentHash * base + nums2[i]) % modulus; if (i == length - 1) { if (hashes.contains(currentHash)) return true; } } else { long prevVal = nums2[i - length]; currentHash = (currentHash - prevVal * power) % modulus; if (currentHash < 0) currentHash += modulus; currentHash = (currentHash * base + nums2[i]) % modulus; if (hashes.contains(currentHash)) return true; } } return false; }}Complexity
Time
O((N + M) * log(min(N, M))). The binary search takes `log(min(N, M))` steps. In each step, the `check` function with rolling hash takes O(N + M) time.
Space
O(min(N, M)) to store the hashes of the subarrays of the smaller array.
Trade-offs
Pros
Asymptotically the fastest solution.
Very efficient for large inputs.
Cons
More complex to implement correctly.
Relies on hashing, which has a theoretical (though extremely small) chance of collision, which could lead to a wrong answer if not handled by secondary verification.
Solutions
Solution
class Solution {public int findLength(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[][] f = new int[m + 1][n + 1]; int ans = 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; ans = Math.max(ans, f[i][j]); } } } return ans; }}/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findLength = function (nums1, nums2) { const m = nums1.length; const n = nums2.length; const f = Array.from({ length: m + 1 }, (_) => new Array(n + 1).fill(0)); let ans = 0; for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; ans = Math.max(ans, f[i][j]); } } } return ans; };class Solution {public: int findLength(vector<int> &nums1, vector<int> &nums2) { int m = nums1.size(), n = nums2.size(); vector<vector<int>> f(m + 1, vector<int>(n + 1)); int ans = 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; ans = max(ans, f[i][j]); } } } return ans; }};''' # only set(), not list() >>> nums1 = [1,2,3,2,1] >>> nums2 = [3,2,1,4,7] >>> nums1 & nums2 Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unsupported operand type(s) for &: 'list' and 'list' ''' class Solution : def findLength ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : m , n = len ( nums1 ), len ( nums2 ) dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] ans = 0 for i in range ( 1 , m + 1 ): for j in range ( 1 , n + 1 ): if nums1 [ i - 1 ] == nums2 [ j - 1 ]: dp [ i ][ j ] = 1 + dp [ i - 1 ][ j - 1 ] ans = max ( ans , dp [ i ][ j ]) return ans ############ class Solution : # also OJ passed, with j iterated reversely def findLength ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : m , n = len ( nums1 ), len ( nums2 ) dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] ans = 0 for i in range ( 1 , m + 1 ): for j in range ( n , 0 , - 1 ): if nums1 [ i - 1 ] == nums2 [ j - 1 ]: dp [ i ][ j ] = 1 + dp [ i - 1 ][ j - 1 ] ans = max ( ans , dp [ i ][ j ]) return ans ############ class Solution : def findLength ( self , A , B ): """ :type A: List[int] :type B: List[int] :rtype: int """ m , n = len ( A ), len ( B ) dp = [[ 0 for j in range ( n + 1 )] for i in range ( m + 1 )] max_len = 0 for i in range ( m + 1 ): for j in range ( n + 1 ): if i == 0 or j == 0 : dp [ i ][ j ] = 0 elif A [ i - 1 ] == B [ j - 1 ]: dp [ i ][ j ] = dp [ i - 1 ][ j - 1 ] + 1 max_len = max ( max_len , dp [ i ][ j ]) return max_lenVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.