LeetCode 718: Maximum Length of Repeated Subarray

Problem Restatement

We are given two integer arrays:

nums1
nums2

We need to return the maximum length of a subarray that appears in both arrays.

A subarray is contiguous.

That means we cannot skip elements.

For example:

[3, 2, 1]

is a subarray of:

[1, 2, 3, 2, 1]

only if those values appear next to each other in that exact order.

The official statement asks for the maximum length of a subarray that appears in both arrays. Example 1 uses nums1 = [1,2,3,2,1] and nums2 = [3,2,1,4,7], where the answer is 3 for [3,2,1].

Input and Output

The function shape is:

class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        ...

Examples

Example 1:

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

The longest common subarray is:

[3, 2, 1]

Its length is:

3

Output:

3

Example 2:

nums1 = [0, 0, 0, 0, 0]
nums2 = [0, 0, 0, 0, 0]

The whole array appears in both arrays.

Output:

5

First Thought: Try Every Pair of Starts

A direct approach is to try every starting index in both arrays.

For every pair:

i in nums1
j in nums2

we compare forward while the values match.

nums1[i] == nums2[j]
nums1[i + 1] == nums2[j + 1]
...

This works, but it repeats many comparisons.

In the worst case, many values are equal, so the same matching suffixes are checked again and again.

Problem With Brute Force

If both arrays have length n, there are O(n^2) pairs of starting indices.

For each pair, we may compare up to O(n) elements.

So the brute force runtime can become:

O(n^3)

We need to reuse previous matching work.

Key Insight

This is similar to longest common substring, but for arrays.

Define:

dp[i][j]

as the length of the longest common subarray ending at:

nums1[i - 1]
nums2[j - 1]

If the two ending values match, then we can extend the previous common subarray:

dp[i][j] = dp[i - 1][j - 1] + 1

If the two ending values do not match, then no common subarray can end at both positions:

dp[i][j] = 0

The answer is the maximum value in the DP table.

Algorithm

Let:

m = len(nums1)
n = len(nums2)

Create a DP table:

dp = [[0] * (n + 1) for _ in range(m + 1)]

Then:

1. Initialize answer = 0.
2. For each i from 1 to m:
   • For each j from 1 to n:
     • If nums1[i - 1] == nums2[j - 1], set dp[i][j] = dp[i - 1][j - 1] + 1.
     • Update answer.
     • If they differ, leave dp[i][j] = 0.
3. Return answer.

Correctness

We prove that dp[i][j] stores the length of the longest common subarray ending exactly at nums1[i - 1] and nums2[j - 1].

If nums1[i - 1] != nums2[j - 1], then no common subarray can end at both positions, because the final elements differ. So dp[i][j] = 0 is correct.

If nums1[i - 1] == nums2[j - 1], then any common subarray ending at these two positions must extend a common subarray ending at nums1[i - 2] and nums2[j - 2]. The longest such previous subarray has length dp[i - 1][j - 1], so the new length is dp[i - 1][j - 1] + 1.

The algorithm computes every pair of ending positions. Every repeated subarray has some ending position in both arrays, so its length appears in the DP table. Taking the maximum over all states gives the length of the longest repeated subarray.

Complexity

Let:

m = len(nums1)
n = len(nums2)

Implementation

class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        m = len(nums1)
        n = len(nums2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]
        answer = 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
                    answer = max(answer, dp[i][j])

        return answer

Code Explanation

We create one extra row and one extra column:

dp = [[0] * (n + 1) for _ in range(m + 1)]

This avoids boundary checks when i = 1 or j = 1.

For each pair of positions:

if nums1[i - 1] == nums2[j - 1]:

we extend the common subarray that ended just before both positions:

dp[i][j] = dp[i - 1][j - 1] + 1

Then we update the best length found so far:

answer = max(answer, dp[i][j])

If the values do not match, the DP value stays 0.

That is correct because a contiguous common subarray cannot end at two different values.

Space-Optimized Implementation

We only need the previous diagonal value.

Using one row, iterate j from right to left so dp[j - 1] still refers to the previous row.

class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        m = len(nums1)
        n = len(nums2)

        dp = [0] * (n + 1)
        answer = 0

        for i in range(1, m + 1):
            for j in range(n, 0, -1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[j] = dp[j - 1] + 1
                    answer = max(answer, dp[j])
                else:
                    dp[j] = 0

        return answer

Space-Optimized Complexity

Example Walkthrough

Use:

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

The matching sequence:

[3, 2, 1]

appears as:

nums1[2:5]
nums2[0:3]

When the DP reaches these matching ending pairs:

So the maximum DP value becomes:

3

Testing

def test_find_length():
    s = Solution()

    assert s.findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]) == 3
    assert s.findLength([0, 0, 0, 0, 0], [0, 0, 0, 0, 0]) == 5
    assert s.findLength([1, 2, 3], [4, 5, 6]) == 0
    assert s.findLength([1], [1]) == 1
    assert s.findLength([1], [2]) == 0
    assert s.findLength([1, 2, 1, 2, 3], [1, 2, 3, 1, 2]) == 3

    print("all tests passed")

test_find_length()

Test coverage: