MediumNo. 0718
Maximum Length of Repeated Subarray — LeetCode 718 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Binary Search, Dynamic Programming, Sliding Window, Hash Function, Rolling Hash
- Reading time
- 2 min
- Source
- leetcode.com
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 ansComplexity
- 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
| No. | Problem | Difficulty |
|---|---|---|
| 0713 | Subarray Product Less Than K | Medium |
| 0209 | Minimum Size Subarray Sum | Medium |
| 0862 | Shortest Subarray with Sum at Least K | Hard |
| 1004 | Max Consecutive Ones III | Medium |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard |
| 2302 | Count Subarrays With Score Less Than K | Hard |
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.