718. Maximum Length of Repeated Subarray

Problem Description

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

Examples:

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

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

Constraints:

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

Python Solution

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

Implementation Notes:

• Uses dynamic programming approach
• Time complexity: O(m * n) where m and n are lengths of input arrays
• Space complexity: O(m * n) for the dp table

Java Solution

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 = 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;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        
        return maxLen;
    }
}

C++ Solution

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

JavaScript Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    let maxLen = 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;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
    }
    
    return maxLen;
};

C# Solution

public 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 = 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;
                    maxLen = Math.Max(maxLen, dp[i, j]);
                }
            }
        }
        
        return maxLen;
    }
}

Implementation Notes:

• Uses dynamic programming approach
• Time complexity: O(m * n) where m and n are lengths of input arrays
• Space complexity: O(m * n) for the dp table