Code Implementation

class Solution:
    def findLength(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_len = 0
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i + 1][j + 1] + 1
                    max_len = max(max_len, dp[i][j])
        return max_len
      

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

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }
}
      

var findLength = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    let maxLen = 0;
    for (let i = m - 1; i >= 0; --i) {
        for (let j = n - 1; j >= 0; --j) {
            if (nums1[i] === nums2[j]) {
                dp[i][j] = dp[i+1][j+1] + 1;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
    }
    return maxLen;
};
      

Problem Description

Given two integer arrays nums1 and nums2, find the maximum length of a subarray that appears in both arrays as a contiguous sequence. The subarray must be continuous (no skipping elements) and appear in both arrays with the same order and length.

• The arrays can have different lengths.
• The subarray must be contiguous in both nums1 and nums2.
• Return the length of the longest such subarray. If there is no common subarray, return 0.

Constraints:

• 1 ≤ nums1.length, nums2.length ≤ 1000
• 0 ≤ nums1[i], nums2[i] ≤ 100

Thought Process

At first glance, this problem seems similar to finding the longest common subsequence, but with a key difference: the common elements must be contiguous in both arrays. A brute-force approach would involve checking every possible subarray of nums1 and seeing if it appears in nums2, but this quickly becomes computationally expensive as the array sizes grow.

To optimize, we look for overlapping subproblems and optimal substructure—hallmarks of dynamic programming (DP) problems. If we can define the problem in terms of smaller subproblems, we can use DP to build up our solution efficiently.

The key insight is: if nums1[i] == nums2[j], then the maximum length of the repeated subarray starting at those indices is one plus the maximum length starting at i+1 and j+1.

Solution Approach

• Step 1: Define the DP Table
  • Create a 2D array dp where dp[i][j] represents the length of the longest common subarray starting at nums1[i] and nums2[j].
• Step 2: Fill the Table from the End
  • We iterate backwards (from the end of both arrays) because the length at dp[i][j] depends on dp[i+1][j+1].
  • If nums1[i] == nums2[j], then dp[i][j] = dp[i+1][j+1] + 1.
  • Otherwise, dp[i][j] = 0 (since the subarray can't be extended from these positions).
• Step 3: Track the Maximum
  • Keep a variable maxLen to store the largest value found in dp as we fill it.
• Step 4: Return the Result
  • After filling the table, return maxLen as the answer.

This approach ensures that every possible pair of starting indices is checked efficiently, and overlapping subproblems are reused.

Example Walkthrough

Let's work through an example:

• nums1 = [1, 2, 3, 2, 1]
• nums2 = [3, 2, 1, 4, 7]

We want to find the longest subarray that appears in both. Scanning visually, we see that [3, 2, 1] appears in both arrays.

1. Start filling the DP table from the end. At each cell dp[i][j], check if nums1[i] == nums2[j].
2. For i=2, j=0: nums1[2]=3, nums2[0]=3 → Match! So dp[2][0]=dp[3][1]+1.
3. Continue for i=3, j=1: nums1[3]=2, nums2[1]=2 → Match! dp[3][1]=dp[4][2]+1.
4. Continue for i=4, j=2: nums1[4]=1, nums2[2]=1 → Match! dp[4][2]=dp[5][3]+1 = 1 (since out of bounds, base case is 0).
5. So, dp[3][1]=1+1=2, dp[2][0]=2+1=3. maxLen is updated to 3.
6. No longer common subarray is found, so the answer is 3.

Time and Space Complexity

• Brute-force Approach:
  • Try every subarray in nums1 and check if it appears in nums2.
  • There are O(N²) subarrays in nums1, each checked in O(M) time.
  • Total complexity: O(N² * M), which is too slow for large arrays.
• Dynamic Programming Approach:
  • We fill a table of size O(N * M), where N and M are the lengths of nums1 and nums2.
  • Each cell is filled in O(1) time.
  • Time Complexity: O(N * M)
  • Space Complexity: O(N * M) for the DP table. (Can be optimized to O(min(N, M)) if needed.)

Summary

The "Maximum Length of Repeated Subarray" problem is efficiently solved using dynamic programming. By recognizing the overlapping subproblems and defining a DP table that captures the length of the longest common subarray starting at each pair of indices, we avoid redundant work and achieve a solution that is both elegant and efficient. The approach builds up from the simplest cases and ensures that the result is found in O(N * M) time, making it suitable for large input sizes.