Maximum Length of Repeated Subarray

Maximum Length of Repeated Subarray

What is this problem about?

The Maximum Length of Repeated Subarray coding problem gives you two integer arrays and asks for the length of the longest subarray (contiguous) that appears in both. Unlike subsequences, subarrays must be contiguous. This is related to the longest common substring problem and is a fundamental dynamic programming exercise with connections to string hashing and binary search.

Why is this asked in interviews?

Citadel, Microsoft, Google, Palantir, and Bloomberg include this problem because it has multiple valid approaches at different complexity levels. The DP solution is clean and O(m*n); the rolling hash + binary search approach is more sophisticated and O((m+n) log(min(m,n))). Discussing trade-offs between these approaches demonstrates depth. It also has practical relevance to diff algorithms and sequence alignment.

Algorithmic pattern used

Dynamic Programming: Define dp[i][j] = length of the longest common subarray ending at A[i-1] and B[j-1]. Transition: if A[i-1] == B[j-1], then dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = 0. The answer is the maximum value in the DP table. Time: O(mn), Space: O(mn) or O(min(m,n)) with rolling array.

Binary Search + Rolling Hash: Binary search on the answer length L. For a given L, hash all subarrays of length L in both arrays and check for a common hash. O((m+n) log(min(m,n))) expected.

Example explanation

A = [1, 2, 3, 2, 1], B = [3, 2, 1, 4, 7]

DP table (key cells):

• A[2]=3, B[0]=3: dp[3][1] = dp[2][0] + 1 = 1
• A[3]=2, B[1]=2: dp[4][2] = dp[3][1] + 1 = 2
• A[4]=1, B[2]=1: dp[5][3] = dp[4][2] + 1 = 3

Maximum = 3. The common subarray is [3, 2, 1].

Common mistakes candidates make

• Confusing subarray with subsequence: Subarrays are contiguous; setting dp[i][j] = dp[i-1][j-1] only when elements match (and 0 otherwise) enforces this.
• Off-by-one in DP indices: Using 0-indexed arrays in the DP without careful boundary setup leads to index errors.
• Not tracking the maximum separately: The answer is the max over all dp[i][j], not dp[m][n].

Interview preparation tip

For the Array Hash Function Rolling Hash Sliding Window Binary Search Dynamic Programming interview pattern, start with the DP solution and then mention the binary search + hashing optimization. The DP is interview-friendly for its clarity; the hashing approach shows depth. Both are worth knowing for companies like Citadel and Palantir that probe multiple solution levels.