Maximum Length of Repeated Subarray (leetcode)

I’m looking at this leetcode question, and am having an issue completing the naive approach. I was able to come to an optimal solution here. But I’m not sure what’s wrong with my naive attempt.

The question is as follows:

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].

Here is my current code:

var findLength = function(a, b) {
    if (a.length === 0 || b.length === 0) {
        return 0;
    }
    
    let aWithoutFinalNumber = a.slice(0, a.length - 1);
    let bWithoutFinalNumber = b.slice(0, b.length - 1);

    let aFinalNumber = a[a.length - 1];
    let bFinalNumber = b[b.length - 1];
    
    // matching numbers
    if(aFinalNumber === bFinalNumber) {
        return 1 + findLength(aWithoutFinalNumber, bWithoutFinalNumber);
    } else { // mismatch. Compete to find the maximum length.
        return Math.max(findLength(a, bWithoutFinalNumber), findLength(aWithoutFinalNumber, b));
    }
};

My solution passes several test cases, but fails on cases like a: [0,1,1,1,1] b: [1,0,1,0,1]. Any insight on my mistake would be appreciated!

Answer

The problem comes from the way you calculate the max length when the last elements match. here is a minimal example:

var findLength = function(a, b) {
    if (a.length === 0 || b.length === 0) {
        return 0;
    }

    let aWithoutFinalNumber = a.slice(0, a.length - 1);
    let bWithoutFinalNumber = b.slice(0, b.length - 1);

    let aFinalNumber = a[a.length - 1];
    let bFinalNumber = b[b.length - 1];

    // matching numbers
    if(aFinalNumber === bFinalNumber) {
        return 1 + findLength(aWithoutFinalNumber, bWithoutFinalNumber); //< -- problem here
    } else { // mismatch. Compete to find the maximum length.
        return Math.max(findLength(a, bWithoutFinalNumber), findLength(aWithoutFinalNumber, b));
    }
};

console.log(findLength([1, 0, 2, 1], [1, 0, 3, 1]));

If there is any match you add 1 to the max length but that’s not necessarily true if there is a mismatch later. Here is a shortened version what happens with illustration for easier understanding:

[1, 0, 2, 1]
          ^-------|
[1, 0, 3, 1]      | -- match, max length +1
          ^-------|
______

[1, 0, 2, 1]
       ^----------|
[1, 0, 3, 1]      | -- mismatch, max length +0
       ^----------|

______

[1, 0, 2, 1]
    ^-------------|
[1, 0, 3, 1]      | -- match, max length +1
    ^-------------|

______

[1, 0, 2, 1]
 ^----------------|
[1, 0, 3, 1]      | -- match, max length +1
 ^----------------|

When you total all the matches, you get 3 however, the count should have been reset when there was a mismatch.

One simple change that can be done to the algorithm to avoid this problem is to pass the current count as an argument to the function. This way, you can control when the count needs to be reset:

var findLength = function(a, b, maxSoFar = 0) { //<-- default count of zero
    if (a.length === 0 || b.length === 0) {
        return maxSoFar; //<-- return the count
    }

    let aWithoutFinalNumber = a.slice(0, a.length - 1);
    let bWithoutFinalNumber = b.slice(0, b.length - 1);

    let aFinalNumber = a[a.length - 1];
    let bFinalNumber = b[b.length - 1];

    // matching numbers
    if(aFinalNumber === bFinalNumber) {
        const newMax = maxSoFar + 1; //<-- increment the count
        return Math.max(newMax, findLength(aWithoutFinalNumber, bWithoutFinalNumber, newMax)); //<-- return the newMax in case the next is a mismatch
    } else { // mismatch. Compete to find the maximum length.
        return Math.max(findLength(a, bWithoutFinalNumber), findLength(aWithoutFinalNumber, b)); //<-- reset the count
    }
};

console.log(findLength([1, 0, 2, 1], [1, 0, 3, 1]));
console.log(findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]));
console.log(findLength([0, 1, 1, 1, 1], [1, 0, 1, 0, 1]));