718. Maximum Length of Repeated Subarray

 

Maximum Length of Repeated Subarray

Problem Description

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

Idea:

A) Brute Force (TLE) Approach

• Loop through all the elements in A and B, and check the corresponding matches
• If the elements match, we check as far as we can and then get the maximum length
• Else we skip

Let`s Code it!

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

var findLength = function(nums1, nums2) {
    let res = 0;
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++) {
            if (nums1[i] == nums2[j]) {
                let k = 1;
                while (i + k < nums1.length && j + k < nums2.length && nums1[i + k] == nums2[j + k]) k++;
                res = Math.max(res, k);
            }
        }
    }
    return res;;
};

Time complexity 

    O(mn^2)

Space complexity 

    O(1)

2) Naive Binary Search Approach

• Having length k subarray appear in both arrays indicates having a shorter length of subarray as well
• Using the above fact, we can use binary search to narrow our search
• We create a separate function check length(x, A, B) to check if there is a length x subarray common to both arrays
• If x is checked, we need to continue searching for the right part, so lo = mi
• Else hi = mi
• However, we need a special formula to take care of the infinite loop to make mi calculation right-leaning

Let`s Code it!

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

var findLength = function(nums1, nums2) {
    let lo = 0, hi = Math.min(nums1.length, nums2.length);
    while (lo < hi) {
        let mi = lo + parseInt((hi - lo + 1) / 2);
        if (checkLength(mi, nums1, nums2)) lo = mi;
        else hi = mi - 1;
    }
    return lo;
};

let checkLength = function( x,  A, B) {
        if (x == 0) return true;
        else if (x > Math.min(A.length, B.length)) return false;
        else {
            let seen = new Set();
            for (let i = 0; i + x <= A.length; i++) {
                seen.add(String(A.slice( i, i + x)));
            }
            for (let i = 0; i + x <= B.length; i++) {
                if (seen.has(String(B.slice(i, i + x)))) {
                    return true;
                }
            }
            return false;
        }
    }

Time complexity: 

      O(mnl(logl)), where m is the length of A, n is the length of B, l is a min of m and n

Space complexity: 

      O(m^2)

3) Dynamic Programming

• Using a similar idea as a typical longest subsequence of string, we use dynamic programming 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])

Let`s Code it!

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const matrix = function ( rows, cols, defaultValue){
  return Array.from(Array(rows), 
     row => Array.from(Array(cols), cell => defaultValue)
  );
}

var findLength = function(nums1, nums2) {
    let m = nums1.length, n = nums2.length;
    let dp = matrix(m+1,n+1,0);
    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (nums1[i] == nums2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                ans = Math.max(ans, dp[i + 1][j + 1]);
            }
        }
    }
    return ans;
};

Time complexity

    O(mn)

Space complexity 

    O(mn)

4) 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 the 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 on the hash, we double-check whether these two subarrays match even if they have the same hash

Let`s Code it (Java)

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;
    }
}

Time complexity 

    O(log(l)(m + n)), where l = min(m, n)

Space complexity 

    O(m + n)

Conclusion

That’s all folks! In this post, we solved LeetCode problem #718. Maximum Length of Repeated Subarray

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!