Maximum Length of Repeated Subarray - Video Solutions

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.