Maximum Length of Repeated Subarray — LeetCode 718 Python Solution

The problem

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Example

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].

Python solution

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

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 718. Maximum Length of Repeated Subarray is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems