MediumNo. 0718

Maximum Length of Repeated Subarray — LeetCode 718 Python Solution

Topics
Array, Binary Search, Dynamic Programming, Sliding Window, Hash Function, Rolling Hash
Reading time
2 min

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

PythonSolution
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

Time
O(n)
Space · auxiliary
O(1) to O(n)

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

Frequently asked questions

How hard is LeetCode 718. Maximum Length of Repeated Subarray?

LeetCode 718. Maximum Length of Repeated Subarray is rated Medium on LeetCode.

What topics does LeetCode 718. Maximum Length of Repeated Subarray cover?

LeetCode 718. Maximum Length of Repeated Subarray is tagged Array, Binary Search, Dynamic Programming, Sliding Window, Hash Function and Rolling Hash on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.