Maximum Length of Repeated Subarray: DP Table Matching

You are given two integer arrays and need to find the longest subarray that appears in both. This is LeetCode 718: Maximum Length of Repeated Subarray, and it is essentially the classic Longest Common Substring problem applied to arrays instead of strings.

If you have solved Longest Common Subsequence, be careful. That problem finds the longest shared subsequence, where elements can be non-contiguous. Here, the shared elements must be contiguous. That single difference changes the recurrence in a way that trips up many people.

The problem

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]  -> 3  (subarray [3,2,1])

The approach

Define dp[i][j] as the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]. The table has (m + 1) rows and (n + 1) columns, where m = len(nums1) and n = len(nums2).

At each cell, you compare nums1[i-1] and nums2[j-1]:

• If they are equal, the common subarray extends from whatever ended one position earlier in both arrays: dp[i][j] = dp[i-1][j-1] + 1.
• If they are not equal, no common subarray can end at both of these positions: dp[i][j] = 0.

You track the global maximum across all cells as you go. The answer is that maximum.

The solution

def findLength(nums1, nums2):
    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

The outer loop iterates over nums1, the inner loop over nums2. When elements match, you extend the diagonal. When they do not match, dp[i][j] stays at its default value of 0. After filling the entire table, result holds the length of the longest common subarray.

Step-by-step walkthrough

Notice how the values 1, 2, 3 form a diagonal in the DP table at positions (3,1), (4,2), (5,3). Each value builds on the one at the top-left diagonal. This diagonal pattern is the signature of a contiguous match. Whenever you see a growing diagonal in this kind of table, you have found a common subarray getting longer.

Complexity analysis

The brute force checks every possible starting pair and extends to find the match length, giving a cubic factor. The DP table eliminates repeated work by storing results for all pairs. You can further optimize space to a single row by noticing that each row only depends on the previous row, but you need to iterate the inner loop in reverse to avoid overwriting values you still need.

The building blocks

2D DP matching pattern

This problem uses the same 2D table structure as several other classic DP problems, but the transition rule is the simplest of the family:

• Longest Common Substring / Repeated Subarray (this problem): match = dp[i-1][j-1] + 1, no match = 0. Finds contiguous matches.
• Longest Common Subsequence (LeetCode 1143): match = dp[i-1][j-1] + 1, no match = max(dp[i-1][j], dp[i][j-1]). Allows non-contiguous matches.
• Edit Distance (LeetCode 72): match = dp[i-1][j-1] (free), no match = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1. Minimizes transformation cost.
• Distinct Subsequences (LeetCode 115): match = dp[i-1][j-1] + dp[i-1][j], no match = dp[i-1][j]. Counts subsequence matches.

All four share the same table shape and the same character-comparison step at each cell. The only difference is what you do with the result: reset to 0, take a max, take a min, or sum.

Edge cases

• No overlap at all: if nums1 and nums2 share no common elements, every cell stays at 0 and the answer is 0.
• One array is a subarray of the other: the answer equals the length of the shorter array. The diagonal will grow to that full length.
• Single-element arrays: if both arrays have one element, the answer is 1 if they match and 0 if they do not.
• All elements identical: if both arrays contain the same repeated value, the answer is min(m, n). The entire diagonal fills up.
• Duplicate values creating multiple diagonals: when the same value appears at multiple positions, you get several diagonals in the table. The answer is the longest one. The running max handles this automatically.

From understanding to recall

You now know how to set up the 2D table, why the recurrence resets to 0 on a mismatch, and how growing diagonals in the table correspond to matching subarrays. But reading through this once is not the same as writing it from memory. In an interview, you need to remember that matching means extending the diagonal by 1, that mismatching means resetting to 0 (not taking a max of neighbors), and that you need a separate variable to track the global maximum since the answer is not simply dp[m][n].

The distinction between this problem and Longest Common Subsequence is subtle but critical. Both use the same table layout and the same comparison step. The difference is a single line: reset to 0 versus take the max of neighbors. If you drill both problems until the transitions are automatic, you will never confuse them.

This 2D matching pattern is one of roughly 60 reusable building blocks in the CodeBricks system. You practice each block individually with spaced repetition until writing the solution from scratch is second nature. Maximum Length of Repeated Subarray, LCS, and Edit Distance together form the core of the two-sequence DP family. Locking them in as a group is the fastest path to owning this entire category.

Related posts

• Longest Common Subsequence - Similar DP table but for subsequences instead of subarrays
• Edit Distance - Another 2D DP problem comparing two sequences
• Distinct Subsequences - DP table for counting subsequence matches