Maximum Length of Repeated Subarray

medium array dp

Problem

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

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

Output3

The longest common contiguous subarray is [3,2,1].

nums1

nums2

def find_length(a, b):
    m, n = len(a), len(b)
    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 a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > best: best = dp[i][j]
    return best

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

class Solution {
    public int findLength(int[] a, int[] b) {
        int m = a.length, n = b.length, best = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (a[i-1] == b[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    best = Math.max(best, dp[i][j]);
                }
        return best;
    }
}

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

Explanation

We want the longest run of numbers that appears contiguously in both arrays. The idea is to compare the two arrays in a grid and track how long a matching streak is as we line up positions.

Let dp[i][j] be the length of the common run that ends exactly at a[i-1] in the first array and b[j-1] in the second. If those two values are equal, the run extends the diagonal before it: dp[i][j] = dp[i-1][j-1] + 1. If they differ, the run is broken and the cell stays 0.

The answer is the largest value anywhere in the table, since a common contiguous subarray must end at some pair of positions. We use an extra zero row and column so the i-1/j-1 lookups never go out of bounds.

This works because a contiguous match of length L lines up as a growing diagonal of L matches in the grid, and the +1-on-match rule rebuilds that chain step by step.

Example: for [1,2,3,2,1] and [3,2,1,4,7], the shared [3,2,1] forms a diagonal that climbs to 3, the answer.

Time: O(m·n) Space: O(m·n)