Maximum Length of Repeated Subarray
Medium · Sliding Window · Array · Binary Search · Dynamic Programming · Sliding Window · Rolling Hash · Hash Function
Problem
Given two integer arrays nums1 and nums2, return the length of the longest contiguous subarray that appears in both arrays: the same values in the same order, with no gaps.
Examples
Input: nums1 = [5,1,2,3,9], nums2 = [0,1,2,3,4] Output: 3
[1,2,3] occurs in both arrays.
Input: nums1 = [7,7], nums2 = [8] Output: 0
The arrays have no value in common.
Input: nums1 = [4,4,6,2,8], nums2 = [6,2,8,4] Output: 3
[6,2,8] ends nums1 and starts nums2.
Constraints
- 1 <= len(nums1), len(nums2) <= 1000
- 0 <= nums1[i], nums2[i] <= 100
Approaches
- Baseline: extend from every pair of starts — time O(n·m·min(n, m)), space O(1)
Follow-up
For much longer arrays, binary search the length L and check whether any window of length L appears in both arrays by comparing rolling hashes of the windows: O((n + m) log min(n, m)) expected time. See the use cases for the same table on two strings and on one array compared with itself.
Related problems
Start free on Cariara · Coding problems · System design studio
