Maximum Length of Repeated Subarray #718

Dynamic Programming Medium

Python Java C++

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

class Solution {    
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int res = 0;
        int dp[][] = new int[n + 1][m + 1];
        
        // Simple DP once you realize it's LCS
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    res = Math.max(res, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return res;
    }
}

#include 
#include 
using namespace std;

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

Problem Statement

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

Detailed Explanation

Approach

This problem is a variation of the Longest Common Substring (LCS) problem. Using dynamic programming, we maintain a 2D array `dp` where `dp[i][j]` represents the maximum length of a subarray ending at `nums1[i-1]` and `nums2[j-1]`.

Key Concepts

1. Dynamic Programming: Store and reuse results of overlapping subproblems.
2. Longest Common Substring: The problem reduces to finding the maximum length of matching prefixes for substrings of the two arrays.

Algorithm Steps

1. Initialize a 2D array `dp` with dimensions `(n+1) x (m+1)` filled with zeros.
2. Iterate through both arrays:
   • If `nums1[i-1] == nums2[j-1]`, set `dp[i][j] = dp[i-1][j-1] + 1`.
   • Update the result with the maximum value of `dp[i][j]`.
3. Return the maximum value found in the `dp` array.

Time and Space Complexity

• Time Complexity: O(n * m)
  • Two nested loops iterate over the two arrays.
• Space Complexity: O(n * m)
  • 2D array `dp` stores intermediate results.

Why This Works

Dynamic programming ensures that all subproblems are solved optimally. The recurrence relation effectively extends the length of matching subarrays while maintaining simplicity and efficiency.

Edge Cases

• One or both arrays are empty: Return `0`.
• Arrays have no common elements: Return `0`.
• Arrays have all elements in common: Return the length of the smaller array.

Common Mistakes

• Not initializing the `dp` array correctly.
• Confusing the indices while comparing elements.
• Using a 1D array instead of a 2D array without modifying the logic.