#718

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Length of Repeated Subarray

Find the maximum length of a subarray that appears in both given integer arrays using dynamic programming.

array binary search dynamic programming sliding window rolling hash

Problem Statement

Given two integer arrays nums1 and nums2, your task is to find the maximum length of a subarray that appears in both arrays. A subarray is a contiguous part of an array.

For example, consider nums1 = [1,2,3,2,1] and nums2 = [3,2,1,4,7]. The longest repeated subarray is [3,2,1], which has length 3. Your solution should efficiently solve this problem by leveraging dynamic programming and optimization techniques.

Examples

Example 1

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

Output: 3

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

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

Solution Approach

State Transition Dynamic Programming

We use dynamic programming to track the longest common subarray. Let dp[i][j] represent the length of the longest common subarray ending at nums1[i] and nums2[j]. If nums1[i] equals nums2[j], then dp[i][j] is dp[i-1][j-1] + 1; otherwise, dp[i][j] is 0.

Binary Search Optimization

We can optimize the solution using binary search to find the maximum subarray length efficiently. This reduces the time complexity by narrowing down the search space for the longest common subarray.

Space Optimization with Rolling Hash

Using a rolling hash technique can help reduce the space complexity by storing only necessary values. This allows us to avoid storing the entire dp table and thus makes the algorithm more memory efficient.

Complexity Analysis

Metric	Value
Time	O((M+N) * \log{(\min(M, N))})
Space	O(M)

The time complexity is O((M+N) * log(min(M, N))) due to binary search and dynamic programming operations. The space complexity is O(M), where M is the length of nums1, because we optimize the space by using only the current row of the dp table.

What Interviewers Usually Probe

Look for an understanding of state transition dynamic programming.
The candidate should propose optimizations such as binary search or rolling hash.
Pay attention to how well they can balance time and space complexity in their approach.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling indices while accessing elements in the dp table.
Over-complicating the solution when a simple dynamic programming approach suffices.
Failing to optimize for space when the problem constraints are large.

Follow-up variants

What if the arrays are very large (greater than 1000 elements)?
Can this problem be solved in linear time?
What if the arrays contain non-integer values or negative numbers?

FAQ

What is the primary approach to solving the Maximum Length of Repeated Subarray problem?

The problem is typically solved using state transition dynamic programming, where dp[i][j] represents the longest common prefix of subarrays starting at nums1[i:] and nums2[j:].

How does dynamic programming help solve the problem?

Dynamic programming is used to efficiently compute the longest common subarray by storing results of overlapping subproblems, reducing redundant calculations.

Can binary search optimize the Maximum Length of Repeated Subarray solution?

Yes, binary search can be used to narrow down the length of the longest common subarray, improving the time complexity of the solution.

What is the time complexity of the Maximum Length of Repeated Subarray problem?

The time complexity is O((M+N) * log(min(M, N))) due to the binary search and dynamic programming steps.

How can space complexity be optimized in this problem?

Space complexity can be optimized by using a rolling hash or by keeping only the current row of the dp table, thus reducing the memory usage.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        ans = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    f[i][j] = f[i - 1][j - 1] + 1
                    ans = max(ans, f[i][j])
        return ans

Continue Practicing

#1477 find two non overlapping sub arrays each with target sum #713 subarray product less than k #689 maximum sum of 3 non overlapping subarrays