Maximum Length of Repeated Subarray (leetcode)

Question

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 1

you can use dp with a table as well. i tried the other code, and it gave errors in cases like: [0,0,0,0,1,0,0] and [0,0,0,0,0,1,0]. Here is a python code for the same.

def findLength(a, b):
    if len(a)==0 or len(b)==0:
        return 0
        
    n=len(a)
    m=len(b)

    dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
    maxSoFar=0
       
    for i in range(1,m+1):
        for j in range(1,n+1):
            if a[j-1]==b[i-1]:
                dp[i][j]=dp[i-1][j-1]+1
                maxSoFar=max(maxSoFar,dp[i][j])
            else:
                dp[i][j]=0
                    
    return maxSoFar

Answer 2

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]));

Answer 3

You could use nested loop and when same element occur in both arrays you could start incrementing both of those indexes until elements in both arrays are the same. The result that gives you the largest set of elements will be the returned result.

function maxSub(a, b) {
  let result = null;

  function findAll(i, j) {
    const res = [];

    if (a[i] !== b[j] || a[i] == undefined || b[j] == undefined) {
      return res;
    }

    return res.concat(a[i], ...findAll(i + 1, j + 1))
  }

  a.forEach((e, i) => {
    b.forEach((c, j) => {
      if (e == c) {
        const sub = findAll(i, j);

        if (!result || sub.length > result.length) {
          result = sub
        }
      }
    })
  })

  return result;
}


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