CODEWITHSUNDEEP
javascript
Ryan Kim
Ryan Kim

Reputation: 101

Avoid using nested loops to find the max-sized sub-string of an array?

Added maximum number according to the input length should be returned.

For example, if the length is 2 then the max among arr[0] + arr[1], arr[1] + arr[2], arr[2] + arr[3] should be returned.

Input is array and length.

I solved this in a real job interview but I think there will be a way not to use nested loop. 

const add = (arr, len) => {
  let rtnVal = 0

  for (let i = len - 1; i < arr.length; i++) {
    let temp_idx = i;
    let temp_sum = 0;
    for (let j = 0; j < len; j++) {
      temp_sum = (temp_sum || 0) + arr[temp_idx]
      temp_idx -= 1
    }

    if (temp_sum > rtnVal) {
      rtnVal = temp_sum
    }
  }

  return rtnVal
}

console.log(add([1, 2, 3, 4, 5, 6, 7, 8, 9], 4))

I expect the output 30

// enhanced nested loop

const add = (arr, len) => {
  let rtnVal = 0;
  for(let i=len-1;i<arr.length;i++){
    let sum = 0
    for(let j=i;j>=i-len+1;j--){
      sum += arr[j]
    }
    if (sum > rtnVal) rtnVal = sum
  }
  return rtnVal

}
console.log(add([9, 9, 9, 4, 5, 6, 7, 8, 9], 3))

Upvotes: 1

Views: 508

Answers (2)

Ouroborus
Ouroborus

Reputation: 16896

Use a moving window. Add up len numbers starting at the beginning. Then continue through the array adding the next number and subtracting the trailing number.

const add = (arr, len) => {
  return arr.reduce((a,v,i,arr) => {
    a.running += v;
    if(i >= len) {
      a.running -= arr[i-len];
    }
    if(i+1 >= len && a.largest < a.running) {
      a.largest = a.running;
    }
    return a;
  }, {
    largest: Number.NEGATIVE_INFINITY,
    running: 0
  }).largest;
}

console.log(add([1,2,3,4,5,6,7,8,9],4)); // 30
console.log(add([-1,-1,-1,-1],2)); // -2
console.log(add([1],1)); // 1

Upvotes: 4

Priyesh Diukar
Priyesh Diukar

Reputation: 2142

Assuming its sorted like your example. You can use negative slice to select from end and then reduce the array.

const add = (arr, len) => arr.slice(len > arr.len ? arr.len : -len).reduce((total, num) => total + num)

console.log(add([1, 2, 3, 4, 5, 6, 7, 8, 9], 4))

Upvotes: 1

Related Questions