718 - Maximum Length of Repeated Subarray

Difficulty: Medium | Pattern: Dynamic Programming (2D) | Company tags: Amazon, Google, Apple

Problem Statement

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  ([3,2,1] appears in both)

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5

Algorithm Flow

Approach: 2D DP — O(mn), O(mn)

Key insight: dp[i][j] = length of longest common subarray ending at nums1[i-1] and nums2[j-1].

• If nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• Otherwise: dp[i][j] = 0 (subarray must be contiguous)

def findLength(nums1: list[int], nums2: list[int]) -> int:
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    result = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i-1] == nums2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                result = max(result, dp[i][j])
    
    return result

Dry Run

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

Key cells (i, j) where nums1[i-1]==nums2[j-1]:

	3	2	1	4	7
1	0	0	1	0	0
2	0	1	0	0	0
3	1	0	0	0	0
2	0	2	0	0	0
1	0	0	3	0	0

Max = 3 ✓ (diagonal of 1→2→3 at positions ending at (5,3))

Space Optimization — O(n)

Only need previous row: iterate i forward and j backward to avoid overwriting.

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * (n + 1)
    result = 0
    for i in range(1, m + 1):
        for j in range(n, 0, -1):  # reverse to use previous i values
            if nums1[i-1] == nums2[j-1]:
                dp[j] = dp[j-1] + 1
                result = max(result, dp[j])
            else:
                dp[j] = 0
    return result

Complexity

Approach	Time	Space
2D DP	O(mn)	O(mn)
1D DP	O(mn)	O(n)