LeetCode 718 - Maximum Length of Repeated Subarray

The problem asks us to find the longest contiguous subarray that appears in both input arrays. A subarray is different from a subsequence because the elements must remain adjacent.

leetcodemediumarraybinary-searchdynamic-programmingsliding-windowrolling-hashhash-function

LeetCode Problem 718

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function

Solution

Problem Understanding

The problem asks us to find the longest contiguous subarray that appears in both input arrays. A subarray is different from a subsequence because the elements must remain adjacent. This distinction is extremely important because many similar problems allow gaps, but this one does not.

We are given two integer arrays, nums1 and nums2. Our task is to determine the maximum possible length of a contiguous sequence that exists in both arrays. The actual subarray does not need to be returned, only its length.

For example, consider:

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

The longest shared contiguous subarray is:

[3,2,1]

Its length is 3, so the answer is 3.

The constraints are relatively small:

  • Each array length is at most 1000
  • Values range from 0 to 100

These constraints strongly suggest that an O(n^2) dynamic programming solution is feasible, because 1000 * 1000 = 1,000,000, which is manageable.

Several edge cases are important to consider:

  • Arrays with all identical values
  • Arrays with no common elements
  • Arrays of length 1
  • Repeated values that create overlapping matching regions
  • Cases where the longest match occurs near the end of the arrays

A naive implementation can easily make mistakes by confusing subsequences with subarrays. Another common bug is failing to reset state when elements stop matching.

Approaches

Brute Force Approach

The brute force solution checks every possible starting position in nums1 against every possible starting position in nums2.

For each pair of starting indices (i, j), we continue moving forward while the elements match:

nums1[i + k] == nums2[j + k]

We count how long the match continues and update the global maximum.

This approach is correct because it explicitly examines every possible aligned subarray pair. If a repeated subarray exists, the brute force method will eventually compare those exact positions and measure its length.

However, the performance is poor. There are O(n * m) starting pairs, and each comparison may scan up to O(min(n, m)) elements. This leads to cubic behavior in the worst case.

Key Insight for an Optimal Solution

The important observation is that contiguous matching behaves similarly to the Longest Common Substring problem.

If:

nums1[i] == nums2[j]

then the length of the repeated subarray ending at those positions depends entirely on the previous positions:

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

Otherwise:

dp[i][j] = 0

This works because contiguous matching requires adjacent elements to continue matching. Once two elements differ, the contiguous streak immediately breaks.

Dynamic programming allows us to reuse previously computed matching lengths instead of repeatedly scanning forward.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m × min(n,m)) O(1) Tries every possible alignment and expands matches manually
Optimal Dynamic Programming O(n × m) O(n × m) Reuses overlapping subproblems to compute matching streaks efficiently

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

  1. Create a 2D DP table where dp[i][j] represents the length of the longest common subarray ending at nums1[i-1] and nums2[j-1].
  2. Initialize the table with zeros. A value of zero means the current elements do not continue a matching contiguous sequence.
  3. Iterate through every index in nums1.
  4. For each element in nums1, iterate through every index in nums2.
  5. Compare the current elements:
  • If nums1[i-1] == nums2[j-1], then the current matching subarray extends the previous diagonal match:
dp[i][j] = dp[i-1][j-1] + 1
  • Otherwise, the contiguous match breaks:
dp[i][j] = 0
  1. After updating each DP cell, update the global maximum length if the current value is larger.
  2. After processing the entire table, return the maximum value found.

Why it works

The DP table maintains an important invariant:

dp[i][j]

always stores the exact length of the longest common contiguous subarray ending at those two positions.

If the current elements match, the only way to extend a contiguous subarray is through the immediately previous pair of indices. Therefore, adding 1 to the diagonal value correctly extends the matching streak.

If the elements differ, continuity is broken, so the value must reset to 0.

Because every possible ending position pair is examined, the algorithm guarantees that the global maximum repeated subarray length is found.

Python Solution

from typing import List

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

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

        max_length = 0

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

        return max_length

The implementation begins by determining the lengths of both arrays. A DP table of size (n + 1) × (m + 1) is created to simplify boundary handling. The extra row and column eliminate the need for special checks when accessing dp[i-1][j-1].

The nested loops iterate through every pair of positions in the two arrays. Whenever matching values are found, the current DP cell becomes one greater than the diagonal predecessor.

The diagonal dependency is critical because contiguous subarrays can only extend from immediately previous matching positions.

The variable max_length tracks the largest matching subarray seen so far. Since every DP cell represents a valid repeated subarray ending at those indices, the maximum over all cells is the final answer.

Go Solution

func findLength(nums1 []int, nums2 []int) int {
    n := len(nums1)
    m := len(nums2)

    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }

    maxLength := 0

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1

                if dp[i][j] > maxLength {
                    maxLength = dp[i][j]
                }
            }
        }
    }

    return maxLength
}

The Go implementation closely mirrors the Python solution. The primary difference is explicit slice allocation for the 2D DP table.

Go arrays and slices are zero-initialized automatically, so unmatched states naturally remain 0.

Integer overflow is not a concern because the maximum possible answer is only 1000.

Unlike Python, Go does not require importing type annotations or helper libraries.

Worked Examples

Example 1

Input:

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

We build the DP table progressively.

i j nums1[i-1] nums2[j-1] Match? dp[i][j] max_length
1 3 1 1 Yes 1 1
2 2 2 2 Yes 1 1
3 1 3 3 Yes 1 1
4 2 2 2 Yes 2 2
5 3 1 1 Yes 3 3

The final maximum becomes 3.

The repeated subarray is:

[3,2,1]

Example 2

Input:

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

Since every element matches, the diagonal values continuously grow.

i j dp[i][j]
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5

The answer becomes 5.

Complexity Analysis

Measure Complexity Explanation
Time O(n × m) Every pair of indices is processed exactly once
Space O(n × m) The DP table stores results for all index pairs

The algorithm uses nested loops over both arrays, giving a total of n * m states. Each state performs only constant-time work.

The DP table requires storing one integer per state, resulting in quadratic space usage.

Test Cases

from typing import List

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

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

        max_length = 0

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

        return max_length

solution = Solution()

assert solution.findLength([1,2,3,2,1], [3,2,1,4,7]) == 3  # standard example
assert solution.findLength([0,0,0,0,0], [0,0,0,0,0]) == 5  # all elements match
assert solution.findLength([1], [1]) == 1  # single matching element
assert solution.findLength([1], [2]) == 0  # single non-matching element
assert solution.findLength([1,2,3], [4,5,6]) == 0  # no common subarray
assert solution.findLength([1,2,3,4], [2,3]) == 2  # subarray inside larger array
assert solution.findLength([1,1,1,1], [1,1]) == 2  # repeated identical values
assert solution.findLength([1,2,3,2,1], [1,2,3,2,1]) == 5  # identical arrays
assert solution.findLength([5,6,7,8], [7,8,9]) == 2  # matching suffix/prefix
assert solution.findLength([1,2,1,2,1], [1,2,1,2,3]) == 4  # overlapping repeated patterns
Test Why
[1,2,3,2,1] vs [3,2,1,4,7] Validates standard overlapping subarray
[0,0,0,0,0] vs [0,0,0,0,0] Tests maximum continuous growth
[1] vs [1] Smallest matching arrays
[1] vs [2] Smallest non-matching arrays
[1,2,3] vs [4,5,6] Ensures zero is returned correctly
[1,2,3,4] vs [2,3] Tests contained subarray
[1,1,1,1] vs [1,1] Validates repeated values
Identical arrays Ensures full-array match works
Matching suffix/prefix Tests edge alignment behavior
Overlapping repeated patterns Validates correct contiguous tracking

Edge Cases

Arrays With No Common Elements

A common mistake is accidentally treating unrelated values as partial matches. For example:

nums1 = [1,2,3]
nums2 = [4,5,6]

No elements match, so every DP cell remains 0. The implementation handles this naturally because values are only extended when the current elements are equal.

Arrays With All Identical Values

Consider:

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

Every diagonal extension continues growing. Some incorrect implementations reset values improperly or fail to track the longest streak. The DP recurrence correctly builds increasing values along the diagonal until the answer reaches the full array length.

Repeated Overlapping Patterns

Cases like:

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

can confuse naive implementations because multiple potential matches overlap. The DP solution avoids ambiguity because each state strictly represents contiguous matches ending at specific indices. This guarantees that overlapping regions are handled correctly without double counting or skipping possibilities.