718. Maximum Length of Repeated Subarray

Description

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

Constraints

• 1 <= nums1.length, nums2.length <= 1000

• 0 <= nums1[i], nums2[i] <= 100

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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].

Example 2

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

Output: 5

Solutions

Solution 1

/**
 * Time complexity : O(M∗N), where M, N are the lengths of A, B.
 * Space complexity : O(M∗N), the space used by dp.
 */

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

Follow up