Sliding Window Pattern

Akhror Khamidov 0
Viewed 38

I am struggling with understanding the this line below:

    tempSum = tempSum - arr[i - num] + arr[i]

I understand the logic which slides one window everytime. For example, after the first round of iteration which results in 2+1+4 =7, and next iteration by subtracting the first integer "2" from the tempSum and adding the next integer "7" to the tempSum without reiterating all over the number again. However, the issue is if "tempSum" is equal to 7 in the first round of iteration then why subtract "num" instead of subtracting the first integer of the array "2"

In my mind, "num" is only needed for how long should iteration be, and not for anything else

Please, elaborate on why "num" is being subtracted

function maxSubarraySum(arr, num) {
  let maxSum = 0
  let tempSum = 0
  if (arr.length < num) return null

  for  (let i = 0; i < num; i++) {
    maxSum += arr[i]
  }
  tempSum = maxSum
  
  for (let i=num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i]
    maxSum = Math.max(maxSum, tempSum)
  }

  return maxSum
}

console.log(maxSubarraySum([2,1,4,7,4,5,2,6,4,3], 3))

sliding-window algorithm javascript
2 Answers

You're nor subtracting num from 7. You're subtracting the value in the array at position i-num.

index    :  0 1 2 3 4 5 6 7 8 9
array arr: [2,1,4,7,4,5,2,6,4,3]
num: 3

To print the first value (index 0) in the array arr to the console, you can write console.log(arr[0]);

That will write 2 to the console.

If you want to print all the values in a loop you can write

for(let i = 0; i < arr.length; i++)
{
  console.log(arr[i]);
}

and that will put

2 
1
4
7
4
5
2
6
4
3

into the console.

If you want to skip the first num elements of the array, instead of let i = 0 write let i = num. So:

for(let i = num; i < arr.length; i++)
{
  console.log(arr[i]);
}

and that will output

7
4
5
2
6
4
3

If you want to access elements relative to the ith element, you need to add or subtract from i. So if i is 5, and you want to access the element at index 9, you'd need to add 4:

console.log(arr[i+4]); 
//outputs 3 if i is 5 because 5+4 is 9 and 3 is at index 9

or you want to access the item with the index of 2, then you need to subtract 3:

console.log(arr[i-3]) 
// outputs 4 if i is 5 because 5-3 is 2, and 4 is at index 2

Here's a working example you can play with:

const arr = [2,1,4,7,4,5,2,6,4,3];

const idxLbl = document.getElementById('idx');
const rngIdx = document.getElementById('rngIdx');
const offsetLbl = document.getElementById('offset');
const rngOffset = document.getElementById('rngOffset');

let index = 0;
rngIdx.addEventListener('change', function(e)
{
  index = parseInt(e.target.value, 10);
  idxLbl.textContent = index;
  rngOffset.min = (9-index)-9;
  rngOffset.max = 9 - index;
  rngOffset.value = rngOffset.min;
  offsetLbl.textContent = rngOffset.value;
  offset = parseInt(rngOffset.min, 10);
  updateArrayItemLabel()
});

let offset = 0;
rngOffset.addEventListener('change', function(e)
{
  offset = parseInt(e.target.value, 10);
  offsetLbl.textContent = offset;
  updateArrayItemLabel();
});

const chosenIndex = document.getElementById('chosenIndex');
const chosenOffset = document.getElementById('chosenOffset');
const arrValue = document.getElementById('arrValue');

function updateArrayItemLabel()
{
  chosenIndex.textContent = index;
  chosenOffset.textContent = offset;
  arrValue.textContent = arr[index+offset];
}
body
{
  font-family:sans, sans-serif;
}
<p>Choose a starting index: <input type="range" id="rngIdx" value="0" min="0" max="9"> Chosen index:<span id="idx">0</span></p>
<p>Choose an offset: <input type="range" id="rngOffset" value="0" min="0" max="9"> Chosen offset:<span id="offset">0</span></p>
<p>Selectected item: <code>arr[<span id="chosenIndex">0</span>+<span id="chosenOffset">0</span>]</code> is <span id="arrValue">2</span></p>

You know that to figure out the next value you subtract the first item outside the window from the sum, and then add the last item inside the window to the sum. The window is num elements wide. If i is the position of the end of the window, the position of the element to subtract is num elements before that. So then the index of the element to subtract is i-num, so when num is 3 and i is 3, the index is 0.

So tempsum = tempsum - arr[i-num] + arr[i], for num = 3 and i = num means tempsum = tempsum - arr[0] + arr[3]. Which is what you're expecting.

Matt Ellen0 

function maxSubarraySum(arr, num) {
  let maxSum = 0
  let tempSum = 0
  if (arr.length < num) return null


  //first iteration of three integers
  for  (let i = 0; i < num; i++) {
    maxSum += arr[i]
  }
  tempSum = maxSum

  //second iteration
  for (let i=num; i < arr.length; i++) {
    console.log(tempSum)
    console.log('next iteration')
    console.log(arr[i], "i")
    console.log(num, "num, consider it as index") 
    console.log(`${tempSum} - ${arr[i-num]} + ${arr[i]}`)
    tempSum = tempSum - arr[i - num] + arr[i]
    maxSum = Math.max(maxSum, tempSum)
  }

  return maxSum
}

console.log(maxSubarraySum([10,50,20,80,30,70,40,10,40,20], 3))

Akhror Khamidov0
Related