718-maximum-length-of-repeated-subarray
Question
https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example:
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
Thought Process
- Brute Force (TLE)
- Loop through all the elements in A and B, and check the corresponding matchness
- If the elements match, we check as far as we can and then get the maximum length
- Else we skip
- Time complexity O(mn^2)
- Space complexity O(1)
- Naive Binary Search
- Having length k subarray appear in both array indicates having shorter length of subarray as well
- Using the above fact, we can use binary search to narrow our search
- We create a separate function checkLength(x, A, B) to check if there is length x subarray common to both arrays
- If x is checked, we need to continue search the right part, so lo = mi
- Else hi = mi
- However, we need special formula to take care of infinite loop to make mi calculation right leaning
- Time complexity O(mnl(logl)), where m is length of A, n is length of B, l is min of m and n
- Space complexity O(m^2)
- Dynamic Programing
- Use similar idea as typical longest subsequence of string, we use dynamic programing to record the best length so far
- If the integers are the same for ith A and jth B element, we set dp[i][j] = dp[i - 1][j - 1] + 1
- Else we set dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
- Time complexity O(mn)
- Space complexity O(mn)
- Binary Search with Rolling Hash
- Instead of using string to check whether the two subarrays are equal, we use hash
- To efficiently calculate the hash, we use rolling hash function, more specifically Rabin-Karp algorithm
- The formula is h(i) = Sum(a[i]p^i) mod M, where i range from 0 to L - 1, calculating the next hash is h(i+1) = [(h(i) - a[0])/p + a[i+1]p^(L - 1)] mod M
- Using a map to store the A's hash and its indices, then we can loop through the hash from B
- Instead of relying in the hash, we double check whether these two subarrays match even if they have same hash
- Time complexity O(log(l)(m + n)), where l = min(m, n)
- Space complexity O(m + n)
Solution
Brute Force
class Solution {
public int findLength(int[] A, int[] B) {
int res = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
if (A[i] == B[j]) {
int k = 1;
while (i + k < A.length && j + k < B.length && A[i + k] == B[j + k]) k++;
res = Math.max(res, k);
}
}
}
return res;
}
}
Naive Binary Search
class Solution {
public int findLength(int[] A, int[] B) {
int lo = 0, hi = Math.min(A.length, B.length);
while (lo < hi) {
int mi = lo + (hi - lo + 1) / 2;
if (checkLength(mi, A, B)) lo = mi;
else hi = mi - 1;
}
return lo;
}
private boolean checkLength(int x, int[] A, int[] B) {
if (x == 0) return true;
else if (x > Math.min(A.length, B.length)) return false;
else {
Set<String> seen = new HashSet<>();
for (int i = 0; i + x <= A.length; i++) {
seen.add(Arrays.toString(Arrays.copyOfRange(A, i, i + x)));
}
for (int i = 0; i + x <= B.length; i++) {
if (seen.contains(Arrays.toString(Arrays.copyOfRange(B, i, i + x)))) {
return true;
}
}
return false;
}
}
}
DP
class Solution {
public int findLength(int[] A, int[] B) {
int m = A.length, n = B.length;
int[][] dp = new int[m + 1][n + 1];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (A[i] == B[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
ans = Math.max(ans, dp[i + 1][j + 1]);
}
}
}
return ans;
}
}
Binary Search with Rolling Hash
import java.math.BigInteger;
class Solution {
private int p = 113;
private int M = 1000000007;
private int pInv = BigInteger.valueOf(p).modInverse(BigInteger.valueOf(M)).intValue();
public int findLength(int[] A, int[] B) {
int lo = 0, hi = Math.min(A.length, B.length);
while (lo < hi) {
int mi = lo + (hi - lo + 1) / 2;
if (checkLength(mi, A, B)) lo = mi;
else hi = mi - 1;
}
return lo;
}
private boolean checkLength(int x, int[] A, int[] B) {
Map<Integer, List<Integer>> map = new HashMap<>();
int k = 0;
for (int h : getHashes2(A, x)) {
map.computeIfAbsent(h, z -> new ArrayList<>()).add(k++);
}
int j = 0;
for (int h : getHashes2(B, x)) {
for (int i : map.getOrDefault(h, new ArrayList<>())) {
if (Arrays.equals(Arrays.copyOfRange(A, i, i + x), Arrays.copyOfRange(B, j, j + x))) return true;
}
j++;
}
return false;
}
private int[] getHashes(int[] a, int L) {
int[] res = new int[a.length - L + 1];
long h = 0, power = 1;
for (int i = 0; i < L - 1; i++) {
h = (h + a[i] * power) % M;
power = (power * p) % M;
}
for (int i = L - 1; i < a.length; i++) {
h = (h + a[i] * power) % M;
res[i - L + 1] = (int) h;
h = (h - a[i - L + 1]) * pInv % M;
}
return res;
}
private int[] getHashes2(int[] a, int L) {
int[] res = new int[a.length - L + 1];
long h = 0, power = 1;
for (int i = 0; i < L - 1; i++) {
h = (h * p % M + a[i]) % M;
power = (power * p) % M;
}
for (int i = L - 1; i < a.length; i++) {
h = (h * p % M + a[i]) % M;
res[i - L + 1] = (int) h;
h = (h - a[i - L + 1] * power) % M;
if (h < 0) h += M;
}
return res;
}
}