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!

VLAZ · Accepted Answer · 2019-12-29 21:57:31Z

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

edited Dec 29, 2019 at 21:57

answered Dec 29, 2019 at 21:44

VLAZ

29.6k9 gold badges65 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

alexnik42 Over a year ago

Actually your solution won't pass this test case - ([0,0,0,0,0,0,1,0,0,0], [0,0,0,0,0,0,0,1,0,0]), right answer is 9, your solution outputs 7. It happens because even in the case, when the last element is the same, you have to examine this result - findLength(a, bWithoutFinalNumber), findLength(aWithoutFinalNumber, b). I suggest using dp for this problem.

VLAZ Over a year ago

@alexnik42 agreed that this is not an optimal solution for any sub-array at any position. It only does a linear scan for directly matching indexes. However, my focus here was correcting OP's current approach with minimal changes to the logic, rather than solving the challenge for OP.

Nenad Vracar · Accepted Answer · 2019-12-29 21:30:06Z

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

AnonBye · Accepted Answer · 2021-07-08 09:28:04Z

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

answered Jul 8, 2021 at 9:28

AnonBye

111 bronze badge

1 Comment

VLAZ Over a year ago

Here is a JavaScript translation of the code

Collectives™ on Stack Overflow

Maximum Length of Repeated Subarray (leetcode)

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related