Maximum Length of Repeated Subarray solution and explanation
Google
9 more videos on this problem
Maximum Length of Repeated Subarray | Dynamic Programming | Leetcode 718Pepcoding · 10:40 · 13K views
Maximum Length of Repeated Subarray (LeetCode 718) | Longest Common Substring | SimplifiedNikhil Lohia · 13:31 · 10K views
Leetcode - Maximum Length of Repeated Subarray (Python)Timothy H Chang · 6:54 · 6K views
Maximum Length of Repeated Subarray | leetcode 718 | Live coding sessionCoding Decoded · 8:49 · 5K views
LeetCode 718. Maximum Length of Repeated SubarrayHappy Coding · 21:57 · 4K views
[Java] Leetcode 718. Maximum Length of Repeated Subarray [DP Subsequence #9]Eric Programming · 14:47 · 3K views
【每日一题】718. Maximum Length of Repeated Subarray, 7/2/2020Huifeng Guan · 11:06 · 2K views
leetCode 718 - Maximum Length of Repeated Subarray | JSer - algorithm & JavaScriptJSer · 36:35 · 1K views
Daily Leetcode #903: Sep 20, 2022 - 718. Maximum Length of Repeated SubarrayProgramming Live with Larry · 6:50 · 1K views
Leetcode 718: Maximum Length of Repeated SubarrayAlgorithms Casts · 13:26 · 182 views
The problem
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.
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
max_len = 0
dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
for i in range(1, len(nums1) + 1):
for j in range(1, len(nums2) + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
max_len = max(max_len, dp[i][j])
return max_lenclass Solution {
public int findLength(int[] nums1, int[] nums2) {
int maxLen = 0;
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
}
}
return maxLen;
}
}#include <vector>
#include <algorithm>
using namespace std;
int findLength(vector<int>& nums1, vector<int>& nums2) {
int maxLen = 0;
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = max(maxLen, dp[i][j]);
}
}
}
return maxLen;
}var findLength = function(nums1, nums2) {
let maxLen = 0;
const dp = Array(nums1.length + 1).fill(0).map(() => Array(nums2.length + 1).fill(0));
for (let i = 1; i <= nums1.length; i++) {
for (let j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
}
}
return maxLen;
};#include <stdio.h>
#include <string.h>
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int dp[nums1Size + 1][nums2Size + 1];
memset(dp, 0, sizeof(dp));
int maxLen = 0;
for (int i = 1; i <= nums1Size; i++) {
for (int j = 1; j <= nums2Size; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) maxLen = dp[i][j];
}
}
}
return maxLen;
}public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
int maxLen = 0;
int[,] dp = new int[nums1.Length + 1, nums2.Length + 1];
for (int i = 1; i <= nums1.Length; i++) {
for (int j = 1; j <= nums2.Length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i, j] = dp[i - 1, j - 1] + 1;
maxLen = Math.Max(maxLen, dp[i, j]);
}
}
}
return maxLen;
}
}Python solution uses a list of lists to implement the DP table. For each pair of indices, it checks for matching elements and updates the max length accordingly.
Time Complexity: O(n * m), Space Complexity: O(n * m).
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.
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
def max_len(n1, n2, addA, addB, length):
k, result = 0, 0
for i in range(length):
if n1[addA + i] == n2[addB + i]:
k += 1
result = max(result, k)
else:
k = 0
return result
max_len_result = 0
for i in range(len(nums1)):
max_len_result = max(max_len_result, max_len(nums1, nums2, i, 0, min(len(nums1) - i, len(nums2))))
for i in range(len(nums2)):
max_len_result = max(max_len_result, max_len(nums1, nums2, 0, i, min(len(nums2) - i, len(nums1))))
return max_len_resultclass Solution {
public int findLength(int[] nums1, int[] nums2) {
int maxLen = 0;
for (int offset = -nums2.length; offset < nums1.length; ++offset) {
int len = 0;
for (int i = Math.max(0, offset), j = Math.max(0, -offset);
i < nums1.length && j < nums2.length; ++i, ++j) {
if (nums1[i] == nums2[j]) {
len++;
maxLen = Math.max(maxLen, len);
} else {
len = 0;
}
}
}
return maxLen;
}
}#include <algorithm>
#include <unordered_map>
using namespace std;
int findLength(vector<int>& nums1, vector<int>& nums2) {
int maxLen = 0;
for (int offset = -nums2.size(); offset < nums1.size(); ++offset) {
int len = 0;
for (int i1Start = max(0, offset), i2Idx = max(0, -offset);
i1Start < nums1.size() && i2Idx < nums2.size();
++i1Start, ++i2Idx) {
if (nums1[i1Start] == nums2[i2Idx]) {
len++;
maxLen = max(maxLen, len);
} else {
len = 0;
}
}
}
return maxLen;
}var findLength = function(nums1, nums2) {
const maxLenCalculator = (n1, n2, offsetA, offsetB, uptoLen) => {
let result = 0, k = 0;
for (let i = 0; i < uptoLen; i++) {
if (n1[offsetA + i] === n2[offsetB + i]) {
k++;
result = Math.max(result, k);
} else {
k = 0;
}
}
return result;
};
let maxLen = 0;
for (let i = 0; i < nums1.length; i++) {
maxLen = Math.max(maxLen, maxLenCalculator(nums1, nums2, i, 0, Math.min(nums2.length, nums1.length - i)));
}
for (let i = 0; i < nums2.length; i++) {
maxLen = Math.max(maxLen, maxLenCalculator(nums1, nums2, 0, i, Math.min(nums1.length, nums2.length - i)));
}
return maxLen;
};#include <stdlib.h>
#include <string.h>
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int L = nums1Size, R = nums2Size, maxLen = 0;
for (int shift = 0; shift < L; shift++) {
int len = 0;
for (int i = 0; i < R; i++) {
if (i - shift >= 0 && nums1[i - shift] == nums2[i]) {
len++;
if (len > maxLen) maxLen = len;
} else {
len = 0;
}
}
}
return maxLen;
}public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
int maxLen = 0;
for (int k = 0; k < nums1.Length; k++) {
int len = 0;
for (int i = k, j = 0; i < nums1.Length && j < nums2.Length; i++, j++) {
if (nums1[i] == nums2[j]) {
len++;
maxLen = Math.Max(maxLen, len);
} else {
len = 0;
}
}
}
for (int k = 0; k < nums2.Length; k++) {
int len = 0;
for (int i = 0, j = k; i < nums1.Length && j < nums2.Length; i++, j++) {
if (nums1[i] == nums2[j]) {
len++;
maxLen = Math.Max(maxLen, len);
} else {
len = 0;
}
}
}
return maxLen;
}
}Python recursively calculates continuous matching segments, updating the result while considering sliding conditions across length variables, achieving memory-lean overlap determinations.
Time Complexity: O(n * m), Space Complexity: O(1).
Approach 3: Default Approach
function findLength(nums1: number[], nums2: number[]): number {
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;
}func findLength(nums1 []int, nums2 []int) (ans int) {
m, n := len(nums1), len(nums2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
f[i][j] = f[i-1][j-1] + 1
if ans < f[i][j] {
ans = f[i][j]
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n * m), Space Complexity: O(n * m). |
| Sliding Window with Hashing | Time Complexity: O(n * m), Space Complexity: O(1). |
| Default Approach | – |
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 |
Frequently asked questions
Is Maximum Length of Repeated Subarray easy or hard?
Maximum Length of Repeated Subarray is generally considered a medium difficulty problem. The DP solution is straightforward once you recognize the longest common substring pattern, but optimizing it with rolling hash and binary search requires deeper algorithm knowledge.
Maximum Length of Repeated Subarray Python/Java solution
Python and Java implementations commonly use a DP table where dp[i][j] stores the length of the longest matching suffix ending at those indices. When nums1[i-1] equals nums2[j-1], the value becomes dp[i-1][j-1] + 1. The alternative optimized solution uses rolling hash with a hash set to detect equal subarrays during binary search.
How to solve Maximum Length of Repeated Subarray in O(n)?
A strict O(n) solution is generally not achievable for two independent arrays. The closest practical optimization uses binary search on the answer combined with rolling hash, giving O((n + m) log(min(n, m))). Each check runs in linear time using sliding window hash updates.
What is the best approach for Maximum Length of Repeated Subarray?
The most straightforward approach is dynamic programming with O(n * m) time complexity. It treats the problem like the longest common substring by extending matches diagonally in a DP table. For larger inputs, a more optimized solution uses binary search combined with rolling hash to check candidate subarray lengths efficiently.
Is Maximum Length of Repeated Subarray asked at Google/Amazon/Meta?
This problem appears frequently in coding interviews because it combines array processing with dynamic programming and hashing. Variants of longest common substring and repeated subarray detection have been reported in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Maximum Length of Repeated Subarray?
The dynamic programming approach uses a 2D DP table to track matching suffix lengths. The optimized solution relies on hash sets and rolling hash values to compare subarrays efficiently while sliding a window across the arrays.
What is the time complexity of Maximum Length of Repeated Subarray?
The classic dynamic programming solution runs in O(n * m) time where n and m are the lengths of the two arrays. An optimized approach using binary search and rolling hash reduces this to roughly O((n + m) log(min(n, m))). Space complexity ranges from O(n * m) in the basic DP table to O(n) with hashing.