Find largest subarray length in JavaScript

Question

I made a function for finding largest subarray length. It works fine but with some input it doesn't show the correct output.

Here is my code:

    function maxLength(a, k) {
      function sumOfArray(arr) {
        return arr.reduce((a, b) => a + b, 0);
      }

      var sub_array = [];
      for (var i = 0; i < a.length; i++) {
        for (var j = i + 1; j < a.length; j++) {
          if (j - i > sub_array.length && sumOfArray(a.slice(i, j)) < k) {
            sub_array = a.slice(i, j);
          }
        }
      }
      return sub_array.length;
    }


console.log(maxLength([3,1,2,1,4], 4))

The input which shows wrong answer is: [3,1,2,1,4] and k = 4 which the output is 2 but the correct answer is 3

How can I fix the code

Any help will be appreciated

So what is an example of an input that is wrong, what is one that is right? — epascarello
– epascarello, Commented Aug 30, 2018 at 14:02
@epascarello I mentioned in the question the case which is wrong and the correct answer for that — Ali Vojdanian
– Ali Vojdanian, Commented Aug 30, 2018 at 14:03
One that works would help as well. But there are two parameters to the function. For what value of k does [3,1,2,1,4] not work? — Scott Sauyet
– Scott Sauyet, Commented Aug 30, 2018 at 14:04
So do expect 3 because it's the length of [1, 2, 1]? If so, then you need to change < k to <= k. — Scott Sauyet
– Scott Sauyet, Commented Aug 30, 2018 at 14:07

NullPointer · Accepted Answer · 2018-08-30 14:14:55Z

1

If I am not wrong the you are trying the subarray with max length whoes sum is as input(k).

For this change in your if condition=> < k to < =k

if (j - i > sub_array.length && sumOfArray(a.slice(i, j)) < k)

to

if (j - i > sub_array.length && sumOfArray(a.slice(i, j)) <= k)

function maxLength(a, k) {
  function sumOfArray(arr) {
    return arr.reduce((a, b) => a + b, 0);
  }

  var sub_array = [];
  for (var i = 0; i < a.length; i++) {
    for (var j = i + 1; j < a.length; j++) {
      if (j - i > sub_array.length && sumOfArray(a.slice(i, j)) <= k) {
        sub_array = a.slice(i, j);
      }
    }
  }
  return sub_array.length;
}
console.log(maxLength([3,1,2,1,4],4));
console.log(maxLength([3,1,2,1,4],7));
console.log(maxLength([1,1,1,1,3,1,2,1,4],7));

edited Aug 30, 2018 at 14:14

answered Aug 30, 2018 at 14:09

NullPointer

7,3885 gold badges30 silver badges43 bronze badges

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

1 Comment

Ali Vojdanian Over a year ago

I have tried this before. But it shows the same output

Ali Vojdanian · Accepted Answer · 2018-09-01 17:00:02Z

1

After testing with different cases finally I got that some part of the code should be changed.

First for loop must i <= a.length and also second for loop j <= a.length

Also in if statement sumOfArray(a.slice(i, j)) < k should be change to:

sumOfArray(a.slice(i, j)) <= k

These changes show the correct answer for all cases.

So here is the code:

function maxLength(a, k) {
function sumOfArray(arr) {
  return arr.reduce((a, b) => a + b, 0);
}

var sub_array = [];
for (var i = 0; i <= a.length; i++) {
  for (var j = i + 1; j <= a.length; j++) {
    if (j - i > sub_array.length && sumOfArray(a.slice(i, j)) <= k) {
      sub_array = a.slice(i, j);
    }
  }
} 
return sub_array.length;

}

answered Sep 1, 2018 at 17:00

Ali Vojdanian

2,1232 gold badges32 silver badges49 bronze badges

Comments

Scott Sauyet · Accepted Answer · 2018-08-30 14:49:18Z

@NullPointer gave the simple modification that seems to make your function work. Here is another approach that I think simplifies the problem:

const sum = (xs) => xs.reduce((a, b) => a + b, 0)
const range = (lo, hi) => [...new Array(hi - lo + 1)].map((_, i) => i + lo);

const subarrays = (arr) => arr
  .map((x, i) => range(i + 1, arr.length + 1).map(j => arr.slice(i, j)))  
  .reduce((a, b) => a.concat(b), [[]])

const maxLength = (arr, limit) => Math.max.apply(null,
  subarrays(arr)
    .filter(xs => sum(xs) <= limit)
    .map(xs => xs.length)
)

console.log(maxLength([3, 1, 2, 1, 4], 4))

sum gives the sum of the values in an array.
range creates an array of numbers between lo and high
subarrays lists the subarrays of an array. For instance subarrays([2, 3, 5]) returns [[], [2], [2, 3], [2, 3, 5], [3], [3, 5], [5]]

and of course

maxLength is the function you're trying to write.

There are certainly potential efficiencies lost in this approach, involving not having to test subarrays that extend one that already exceeds the limit. But those efficiencies are not used in the original either.

sum and range here are clearly reusable functions, and it's possible that subarrays might also come in handy.

Steve Taylor · Accepted Answer · 2020-09-29 06:42:37Z

0

A few issues with the above:

is not defensive (i could also check type in my code)
starts at the smallest blocks, do the biggest spans first so you can terminate early

Try:

function maxLength(a, k) {
  if(!a || !k) return 0
  for(let scanlen = a.length; scanlen; scanlen--){
    for(let start = 0; start+scanlen<=a.length; start++){
      if( a.slice(start, start+scanlen).reduce((acc,curr)=> acc+curr ) <= k)
         return scanlen
    }
  }
  return 0
}

edited Sep 29, 2020 at 6:42

answered Sep 29, 2020 at 4:39

Steve Taylor

4481 gold badge4 silver badges11 bronze badges

Collectives™ on Stack Overflow

Find largest subarray length in JavaScript

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related