Maximum Length of Repeated Subarray

LeetCode Q 718 - Maximum Length of Repeated Subarray

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

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

Solution

Since a common subarray of A and B must start at some A[i] and B[j], let 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 maxLen(dp[i][j]) over all i, j.

Time Complexity: O(M * N);

Space Complexity: O(M * N);

M, N: length of A, B

Code:

public int findLength(int[] A, int[] B) {
	int[] dp = new int[A.length + 1][B.length + 1];
	int res = 0;
	for (int i = 1; i < dp.length; i++) {
		for (int j = 1; i < dp[0].length; j++) {
			if (A[i - 1] == B[j - 1]) 
				dp[i][j] = dp[i - 1][j - 1] + 1;
			res = Math.max(res, dp[i][j]);
		}
	}
	return res;
}

An Optimized Solution

We can optimize the space complexity.
dp[i][j] = dp[i-1][j-1] + 1 –> maxLen[i][j] only depends on maxLen[i-1][j-1], so you only need to keep maxLen[i-1][j-1] which is one element.
Therefore, we use maxLenTemp to keep maxLen[i-1][j-1] and traverse the matrix diagonally.

Time Complexity: O(M * N);

Space Complexity: O(1);

M, N: length of A, B

Code: Optimzed Solution

public int findLength(int[] A, int[] B) {
	int res = 0;
	for (int i = 0; i < B.length; i++) {
		int maxLenTemp = 0;
		for (int m = 0, n = i; m < A.length && n < B.length; m++, n++) {
			if (A[m] == B[n]) {
				maxLenTemp++;
				res = Math.max(res, maxLenTemp);
			} else {
				maxLenTemp = 0;
			}
		}
	}
	for (int i = 1; i < A.length; i++) {
		int maxLenTemp = 0;
		for (int m = i, n = 0; m < A.length && n < B.length; m++, n++) {
			if (A[m] == B[n]) {
				maxLenTemp++;
				res = Math.max(res, maxLenTemp);
			} else {
				maxLenTemp = 0;
			}
		}
	}
	return res;
}