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);
            }
    
        }
    }
    
  • // OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
    // Time: O(MN)
    // Space: O(min(M, N))
    class Solution {
    public:
        int findLength(vector<int>& A, vector<int>& B) {
            if (A.size() < B.size()) swap(A, B);
            int M = A.size(), N = B.size(), ans = 0;
            vector<int> dp(N + 1, 0);
            for (int i = 0; i < M; ++i) {
                for (int j = N - 1; j >= 0; --j) {
                    dp[j + 1] = A[i] == B[j] ? 1 + dp[j] : 0;
                    ans = max(ans, dp[j + 1]);
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def findLength(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: int
            """
            m, n = len(A), len(B)
            dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
            max_len = 0
            for i in range(m + 1):
                for j in range(n + 1):
                    if i == 0 or j == 0:
                        dp[i][j] = 0
                    elif A[i - 1] == B[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                        max_len = max(max_len, dp[i][j])
            return max_len
    

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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
    // Time: O(MN)
    // Space: O(min(M, N))
    class Solution {
    public:
        int findLength(vector<int>& A, vector<int>& B) {
            if (A.size() < B.size()) swap(A, B);
            int M = A.size(), N = B.size(), ans = 0;
            vector<int> dp(N + 1, 0);
            for (int i = 0; i < M; ++i) {
                for (int j = N - 1; j >= 0; --j) {
                    dp[j + 1] = A[i] == B[j] ? 1 + dp[j] : 0;
                    ans = max(ans, dp[j + 1]);
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def findLength(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: int
            """
            m, n = len(A), len(B)
            dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
            max_len = 0
            for i in range(m + 1):
                for j in range(n + 1):
                    if i == 0 or j == 0:
                        dp[i][j] = 0
                    elif A[i - 1] == B[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                        max_len = max(max_len, dp[i][j])
            return max_len
    

All Problems

All Solutions