Formatted question description: https://leetcode.ca/all/718.html

718. Maximum Length of Repeated Subarray

Level

Medium

Description

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

Example 1:

Input:

A: [1,2,3,2,1]

B: [3,2,1,4,7]

Output: 3

*8Explanation: **

The repeated subarray with maximum length is [3, 2, 1].

Note:

  1. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

Solution

Use dynamic programming. Create a 2D array dp of A.length + 1 rows and B.length + 1 columns, where dp[i][j] represents the maximum length of repeated subarray of the two subarray A[i..] and B[j..].

Initially, all elements in dp are 0. For i from A.length - 1 to 0 and j from B.length - 1 to 0, if A[i] == B[j], then there is a repeated subarray that starts from index i in A and index j in B, so update dp[i][j] = dp[i + 1][j + 1] + 1, and update the maximum length of a repeated subarray. Finally, return the maximum length of a repeated subarray.

Java

public class Maximum_Length_of_Repeated_Subarray {

    // time: O(M*N)
    // space: O(M*N)
    class Solution {
        public int findLength(int[] A, int[] B) {
            int ans = 0;

            // dp[i][j] be the longest common prefix of A[i:] and B[j:].
            // Whenever A[i] == B[j], we know dp[i][j] = dp[i+1][j+1] + 1.
            // Also, the answer is max(dp[i][j]) over all i, j
            int[][] memo = new int[A.length + 1][B.length + 1];

            for (int i = A.length - 1; i >= 0; --i) {
                for (int j = B.length - 1; j >= 0; --j) {
                    if (A[i] == B[j]) {
                        memo[i][j] = memo[i+1][j+1] + 1;
                        if (ans < memo[i][j]) ans = memo[i][j];
                    }
                }
            }
            return ans;
        }
    }


    class Solution_overTime {

        int max = 0;

        public int findLength(int[] A, int[] B) {

            if (A == null || B == null || A.length == 0 || B.length == 0) {
                return 0;
            }

            for (int i = 0; i < A.length; i++) {
                int c = A[i];

                // look for possible match in array B
                for (int j = 0; j < B.length; j++) {
                    if (B[j] == c) {
                        checkSubLength(A, B, i, j);
                    }
                }
            }

            return max;
        }

        private void checkSubLength(int[] A, int[] B, int i, int j) {

            int count = 0;

            while (i < A.length && j < B.length && A[i++] == B[j++]) {
                count++;
            }
            this.max = Math.max(this.max, count);
        }

    }
}

Java

class Solution {
    public int findLength(int[] A, int[] B) {
        int maxLength = 0;
        int length1 = A.length, length2 = B.length;
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = length1 - 1; i >= 0; i--) {
            for (int j = length2 - 1; j >= 0; j--) {
                if (A[i] == B[j]) {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength;
    }
}

All Problems

All Solutions