LeetCode: Maximum Length of Repeated Subarray Posted on January 19, 2018July 26, 2020 by braindenny Maximum Length of Repeated Subarray Similar Problems: Longest Substring Without Repeating Characters Minimum Window Substring Repeated Substring Pattern CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #inspiring, #dynamicprogramming 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) // 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) // 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 } Post Views: 5 Post navigation LeetCode: Contains Duplicate IILeetCode: Implement Trie (Prefix Tree) Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website