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] <= 100The goal in #718 Maximum Length of Repeated Subarray is to find the longest contiguous segment that appears in both arrays. A common strategy is Dynamic Programming. Define dp[i][j] as the length of the longest common suffix of subarrays ending at nums1[i-1] and nums2[j-1]. If the elements match, extend the previous suffix; otherwise reset to zero. Track the maximum value while filling the table.
Another efficient idea combines Binary Search with a Rolling Hash. Binary search the answer length and use hashing to check whether any subarray of that length appears in both arrays. This reduces comparisons and works well for large inputs.
A sliding window alignment technique can also compare overlapping segments of the two arrays without extra memory. The DP method is straightforward, while the rolling-hash approach improves scalability for larger constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming | O(n × m) | O(n × m) or O(min(n, m)) with optimization |
| Binary Search + Rolling Hash | O((n + m) log(min(n, m))) | O(n) |
| Sliding Window Alignment | O(n × m) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming. dp[i][j] will be the longest common prefix of A[i:] and B[j:].
The answer is max(dp[i][j]) over all i, j.
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) 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.
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.
Time Complexity: O(n * m), Space Complexity: O(1).
1class
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The key difference is that this problem requires the elements to be contiguous, forming a subarray. Longest Common Subsequence allows skipping elements, which changes the DP transition rules and solution structure.
Yes, variations of longest common subarray or substring problems frequently appear in technical interviews at large tech companies. They test understanding of dynamic programming, hashing, and array comparison techniques.
Dynamic programming tables are commonly used to track matching suffix lengths between the two arrays. In optimized solutions, hash sets or rolling hash structures help detect matching subarrays efficiently during binary search.
A common optimal strategy uses dynamic programming where dp[i][j] stores the length of the common suffix ending at two indices. For larger inputs, binary search combined with rolling hash can reduce repeated comparisons and improve performance.
Python recursively calculates continuous matching segments, updating the result while considering sliding conditions across length variables, achieving memory-lean overlap determinations.