Problem statement

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

A subarray is a contiguous slice.

Example 1

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray is [3,2,1].

Example 2

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

Example 3

Input: nums1 = [1,2], nums2 = [3,4]
Output: 0

Constraints

• 1 <= nums1.length, nums2.length <= 30
• 0 <= nums1[i], nums2[j] <= 20

Hints for Maximum Length of Repeated Subarray

1. Hint 1

   Let dp[i][j] be the length of the common run ending at nums1[i-1] and nums2[j-1].

2. Hint 2

   Equal elements extend the diagonal: dp[i][j] = dp[i-1][j-1] + 1. Unequal elements reset it to 0.

3. Hint 3

   The answer is the maximum entry anywhere in the table — not dp[m][n], which is the common suffix.

How to solve Maximum Length of Repeated Subarray

dp[i][j] is the length of the common run ending at nums1[i-1] and nums2[j-1]; equal elements extend the diagonal, unequal ones reset it, and the answer is the largest entry anywhere.

Approach

1. Allocate (m+1) × (n+1) zeros.
2. If nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1 and update the best.
3. Return the best.

Why it works

A common subarray must be contiguous in both arrays, so it lies on a diagonal of the table; the recurrence measures the diagonal run ending at each cell.

Complexity

• Time — O(m · n)
• Space — O(m · n), reducible to one row

Pitfalls

• dp[m][n] is the common suffix, not the answer — take the maximum over the whole table.
• The LCS recurrence (max of up/left) is a different problem.

Reference solution

Python

def findLength(nums1, nums2) -> int:
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 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
                best = max(best, dp[i][j])
    return best

Java

public static int findLength(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[][] dp = new int[m + 1][n + 1];
    int best = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > best) best = dp[i][j];
            }
        }
    }
    return best;
}

C++

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int m = (int) nums1.size(), n = (int) nums2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int best = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                best = max(best, dp[i][j]);
            }
        }
    }
    return best;
}

JavaScript

var findLength = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = [];
    for (let i = 0; i <= m; i++) dp.push(new Array(n + 1).fill(0));
    let best = 0;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > best) best = dp[i][j];
            }
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium