Welcome to Subscribe On Youtube
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
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
Note:
- 1 <= len(A), len(B) <= 1000
- 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.
-
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); } } }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; } } ############ class Solution { public int findLength(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[][] f = new int[m + 1][n + 1]; int ans = 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; ans = Math.max(ans, f[i][j]); } } } return ans; } } -
// 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, nums1: List[int], nums2: List[int]) -> int: m, n = len(nums1), len(nums2) dp = [[0] * (n + 1) for _ in range(m + 1)] ans = 0 for i in range(1, m + 1): for j in range(1, n + 1): if nums1[i - 1] == nums2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1] ans = max(ans, dp[i][j]) return ans class Solution: # also OJ passed, with j interated reversely def findLength(self, nums1: List[int], nums2: List[int]) -> int: m, n = len(nums1), len(nums2) dp = [[0] * (n + 1) for _ in range(m + 1)] ans = 0 for i in range(1, m + 1): for j in range(n, 0, -1): if nums1[i - 1] == nums2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1] ans = max(ans, dp[i][j]) 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 -
func findLength(nums1 []int, nums2 []int) (ans int) { m, n := len(nums1), len(nums2) f := make([][]int, m+1) for i := range f { f[i] = make([]int, n+1) } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if nums1[i-1] == nums2[j-1] { f[i][j] = f[i-1][j-1] + 1 if ans < f[i][j] { ans = f[i][j] } } } } return ans } -
function findLength(nums1: number[], nums2: number[]): number { const m = nums1.length; const n = nums2.length; const f = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0)); let ans = 0; for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; ans = Math.max(ans, f[i][j]); } } } return ans; } -
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findLength = function (nums1, nums2) { const m = nums1.length; const n = nums2.length; const f = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0)); let ans = 0; for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; ans = Math.max(ans, f[i][j]); } } } return ans; };