algoadvance

Leetcode 718. Maximum Length of Repeated Subarray

Problem Statement

You are given two integer arrays nums1 and nums2. Find the length of the maximum length subarray that appears in both arrays.

Clarifying Questions

1. Input Constraints:
   • What are the size limits of nums1 and nums2?
   • What is the range of values for the integers in the arrays?

   Constraints:

   • 1 <= nums1.length, nums2.length <= 1000
   • 0 <= nums1[i], nums2[i] <= 100
2. Edge Cases:
   • What should be returned if there are no common subarrays between the two arrays?

   Answer: Return 0.

Strategy

To solve the problem, we’ll use a dynamic programming (DP) approach. We can maintain a 2D DP array where dp[i][j] represents the length of the longest subarray ending at positions i in nums1 and j in nums2.

Steps:

1. Initialization:
   • Create a 2D array dp with dimensions (len1 + 1) x (len2 + 1) and initialize all elements to 0.
2. DP Transitions:
   • Iterate through each element of nums1 (i from 1 to len1) and nums2 (j from 1 to len2).
   • If nums1[i-1] equals nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
   • Keep track of the maximum value in the dp table, which will be the length of the longest common subarray.
3. Result:
   • The result will be the maximum value found in the DP table.

Time Complexity

• Time Complexity: O(len1 * len2), where len1 and len2 are the lengths of nums1 and nums2, respectively. This is because we use nested loops to fill the DP table.
• Space Complexity: O(len1 * len2) for storing the DP table.

Code

public class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1]; // Create DP table
        
        int maxLength = 0; // To keep track of the maximum length of the common subarray
        
        // Fill the DP table
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // If elements match, increment length
                    maxLength = Math.max(maxLength, dp[i][j]); // Update maxLength
                }
            }
        }
        
        return maxLength; // Return the maximum length found
    }
}

With this solution, you should be able to determine the length of the maximum length subarray that appears in both input arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?