718. Maximum Length of Repeated Subarray

718. Maximum Length of Repeated Subarray (Medium)

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

 

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5

 

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

Companies:
Karat, Indeed, Apple, Amazon, Intuit, Wayfair

Related Topics:
Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function

Similar Questions:

• Minimum Size Subarray Sum (Medium)

Solution 1. DP

Let dp[i + 1][j + 1] be the lenght of the maximum subarray that appears in both the tail of A and B.

dp[i + 1][j + 1] = 1 + dp[i][j]     // A[i] == B[j]
                 = 0                // A[i] != B[j]

Since dp[i + 1][j + 1] only depends on dp[i][j], we can use 1D array to store the dp array.

// OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. Binary Answer + Rolling Hash

Use binary answer to search the maximum length.

For a given length len, generate the rolling hash on A and B and see if there is any hash showing up for both array.

Without hash conflict check (unsafe):

// OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// Author: github.com/lzl124631x
// Time: O((A + B)log(min(A, B)))
// Space: O(max(A, B))
class Solution {
    bool valid(vector<int> &A, vector<int> &B, int len) {
        unsigned long long d = 16777619, h = 0, p = 1;
        unordered_set<unsigned long long> s;
        for (int i = 0; i < A.size(); ++i) {
            h = h * d + A[i];
            if (i < len) p *= d;
            else h -= A[i - len] * p;
            if (i >= len - 1) s.insert(h);
        }
        h = 0;
        for (int i = 0; i < B.size(); ++i) {
            h = h * d + B[i];
            if (i >= len) h -= B[i - len] * p;
            if (i >= len - 1 && s.count(h)) return true;
        }
        return false;
    }
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int L = 0, R = min(A.size(), B.size());
        while (L < R) {
            int M = (L + R + 1) / 2;
            if (valid(A, B, M)) L = M;
            else R = M - 1;
        }
        return L;
    }
};

With hash conflict check:

// OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// Author: github.com/lzl124631x
// Time: O((A + B)log(min(A, B)))
// Space: O(A + B)
class Solution {
    typedef unsigned long long ULL;
    vector<ULL> rolling(vector<int> &A, int len) {
        unsigned long long d = 16777619, h = 0, p = 1;
        vector<ULL> ans;
        for (int i = 0; i < A.size(); ++i) {
            h = h * d + A[i];
            if (i < len) p *= d;
            else h -= A[i - len] * p;
            if (i >= len - 1) ans.push_back(h);
        }
        return ans;
    }
    bool valid(vector<int> &A, vector<int> &B, int len) {
        unordered_map<ULL, vector<int>> m;
        auto ra = rolling(A, len), rb = rolling(B, len);
        for (int i = 0; i < ra.size(); ++i) m[ra[i]].push_back(i);
        for (int i = 0; i < rb.size(); ++i) {
            if (m.count(rb[i]) == 0) continue;
            for (int j : m[rb[i]]) {
                if (equal(begin(A) + j, begin(A) + j + len, begin(B) + i)) return true;
            }
        }
        return false;
    }
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int L = 0, R = min(A.size(), B.size());
        while (L < R) {
            int M = (L + R + 1) / 2;
            if (valid(A, B, M)) L = M;
            else R = M - 1;
        }
        return L;
    }
};

Precompute hashes:

// OJ: https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// Author: github.com/lzl124631x
// Time: O((A + B)log(min(A, B)))
// Space: O(A)
const int maxN = 1001;
class Solution {
    typedef unsigned long long ULL;
    ULL ha[maxN], hb[maxN], p[maxN], d = 16777619;
    ULL hash(ULL *h, int begin, int end) {
        return h[end] - h[begin] * p[end - begin];
    }
    bool valid(vector<int> &A, vector<int> &B, int len) {
        unordered_map<ULL, vector<int>> m;
        for (int i = 0; i + len <= A.size(); ++i) m[hash(ha, i, i + len)].push_back(i);
        for (int i = 0; i + len <= B.size(); ++i) {
            ULL h = hash(hb, i, i + len);
            if (m.count(h) == 0) continue;
            for (int j : m[h]) {
                if (equal(begin(A) + j, begin(A) + j + len, begin(B) + i)) return true;
            }
        }
        return false;
    }
public:
    int findLength(vector<int>& A, vector<int>& B) {
        p[0] = 1;
        for (int i = 0; i < A.size() || i < B.size(); ++i) {
            p[i + 1] = p[i] * d;
            if (i < A.size()) ha[i + 1] = ha[i] * d + A[i];
            if (i < B.size()) hb[i + 1] = hb[i] * d + B[i];
        }
        int L = 0, R = min(A.size(), B.size());
        while (L < R) {
            int M = (L + R + 1) / 2;
            if (valid(A, B, M)) L = M;
            else R = M - 1;
        }
        return L;
    }
};