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.

Description Hints 2 Solution Video 10:40

718. Maximum Length of Repeated Subarray

Medium51.5% acceptance7 companies

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 <= 1000
0 <= nums1[i], nums2[i] <= 100

Asked at 7 companies

Citadel Palantir Netflix Bloomberg

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Use dynamic programming. dp[i][j] will be the longest common prefix of A[i:] and B[j:].

Hint 2

The answer is max(dp[i][j]) over all i, j.

10:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution