Domain 2MediumMEDIUM

Maximum Length of Repeated Subarray

LeetCode problem 718: Maximum Length of Repeated Subarray (medium).

Domain: medium•Updated: 2026-08-30
#Array#Hash Table#Binary Search#Dynamic Programming

Problem Breakdown

We are given two integer arrays, A and B, representing sequences of numbers. Our goal is to find the length of the longest contiguous subarray (substring) that exists in both arrays simultaneously.

Key Distinction: This is a “Longest Common Substring” problem, not Longest Common Subsequence. Order matters, and elements must be adjacent.

  • Inputs: Two lists A and B.
  • Output: An integer representing the maximum length of matching contiguous subarray.
  • Constraints: Lengths up to 1000; values between 0-99. This suggests an O(N2)O(N^2) solution is acceptable (10610^6 operations).
  • Edge Cases:
    • No common elements (return 0).
    • Arrays are identical (return length of array).
    • Single element matches.

Intuition

A brute-force approach would be to generate every possible subarray from A and check if it exists in B. Generating all subarrays takes O(N2)O(N^2), and checking existence naively adds another factor, leading to roughly O(N⋅M⋅K)O(N \cdot M \cdot K) or worse. This is inefficient for large inputs.

The key insight here is that this problem exhibits optimal substructure and overlapping subproblems, which screams Dynamic Programming (DP). Consider the state dp[i][j]: “What is the length of the common suffix ending at index i in A and index j in B?”

  • If A[i] == B[j], then we extend the match found previously: dp[i][j] = dp[i-1][j-1] + 1.
  • If they don’t match, the contiguous sequence breaks at this point for these indices specifically: dp[i][j] = 0.

We iterate through all pairs and maintain a global maximum. This reduces complexity significantly compared to brute force string matching.

Approach

  1. Initialize a DP table of size (len(A) + 1) x (len(B) + 1) with zeros. The extra row/column handles the base case where one array is empty or we are looking back at an imaginary match before index -1.
  2. Iterate through every element i in A and every element j in B using nested loops.
  3. Check if A[i] == B[j].
    • If true: The current common length is the previous diagonal value (dp[i-1][j-1]) plus one. Update current_max with this new length.
    • If false: Reset to zero (since contiguity requires a match).
  4. Return the maximum value recorded in any cell of the DP table.

Complexity Analysis

  • Time Complexity: O(N⋅M)O(N \cdot M), where N and M are lengths of A and B respectively. We visit every pair exactly once. Given constraints (N=1000N=1000), this is roughly 10610^6 operations, well within time limits for Python (typically ~2-3 seconds allowed).
  • Space Complexity: O(N⋅M)O(N \cdot M) to store the DP table.
    • Note: This can be optimized to O(min⁡(N,M))O(\min(N, M)) by only storing two rows (current and previous), but given memory limits are not tight here (10610^6 integers is ~4MB in C++, slightly more in Python objects) and readability is paramount for an interview walkthrough, the full table approach demonstrates clarity of state.

Solution

class Solution:
    def findLength(self, A: list[int], B: list[int]) -> int:
        n = len(A)
        m = len(B)
        
        # Initialize DP table with zeros. 
        # dp[i][j] stores the length of common suffix ending at A[i-1] and B[j-1].
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        
        max_len = 0
        
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if A[i - 1] == B[j - 1]:
                    # Extend the match from diagonal predecessor
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    
                    # Update global maximum found so far
                    max_len = max(max_len, dp[i][j])
                else:
                    # Contiguous sequence broken; reset to zero for this specific pair
                    dp[i][j] = 0
        
        return max_len

Edge Cases Handled

  • No Common Elements: The loops run but max_len remains initialized at 0, which is returned correctly.
  • Identical Arrays: Every cell where indices align will increment the diagonal value up to length N; returns correct full length.
  • Single Element Match: If only one number matches in a specific position, DP increments from base case (0) to 1 and updates max_len.
  • Empty Input Logic: While constraints say len >= 1, if inputs were empty (n=0 or m=0), the loops range(1, n+1) would not execute, returning 0 correctly without crashing.