Leetcode: Maximum Length of Repeated Subarray

Maximum Length of Repeated Subarray



Similar Problems:


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

Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution1: dp: Time O(n*m), Space O(n*m)
// Blog link: https://code.dennyzhang.com/maximum-length-of-repeated-subarray
// Basic Ideas: dynamic programming
//
//   Let's say the common subarray starts with A[i] and B[j]
//   If A[i] == B[j], then dp[i][j] = dp[i]
//   Otherwise dp[i][j] = 0
//  So from right to left, we get dp[][]
//  Then find the maximum
//
// To save the code of base case, we add an extra line and column
//
// Complexity: Time O(n*m), Space O(n*m)
func findLength(A []int, B []int) int {
    len_a, len_b := len(A), len(B)
    dp := make([][]int, len_a+1)
    for i:=0; i<len_a+1; i++ { dp[i] = make([]int, len_b+1) }
    // A: [1,2,3,2,1]
    // B: [3,2,1,4]
    res := 0
    // dp
    for i := len_a-1; i>=0; i-- {
        for j := len_b-1; j>=0; j-- {
            if A[i] == B[j] {
                dp[i][j] = dp[i+1][j+1] + 1
                if dp[i][j] > res { res = dp[i][j]}
            }
        }
    }
    return res
}

  • – Solution2: dp: Time O(n*m), Space O(n+m)
// Blog link: https://code.dennyzhang.com/maximum-length-of-repeated-subarray
//
// From right to left
//
// dp[i][j] only depend on dp[i+1][j+1].
// So Instead of 2D array, we use 2 1D array
//
// Complexity: Time O(n*m), Space O(m)
func findLength(A []int, B []int) int {
    len_a, len_b := len(A), len(B)
    dp := make([]int, len_b+1)
    // A: [1,2,3,2,1]
    // B: [3,2,1,4]
    res := 0
    // dp
    for i := len_a-1; i>=0; i-- {
        dp2 := make([]int, len(dp))
        copy(dp2, dp)
        for j := len_b-1; j>=0; j-- {
            if A[i] == B[j] {
                dp2[j] = dp[j+1] + 1
                if dp2[j]> res { res = dp2[j] }
            }
        }
        copy(dp, dp2)
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.