Sliding window over Array in JavaScript

Question

I need a sliding window over an Array in JavaScript.

For example, a sliding window of size 3 over [1,2,3,4,5,6,7,8,9] shall compute the sequence [[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9]].

The following is my attempt, because I couldn't find a readymade solution:

function window(a, sz) {
  return a.map((_, i, ary) => ary.slice(i, i + sz)).slice(0, -sz + 1);
}

It returns an array of windows that can be mapped over to get the individual windows.

What is a better solution?

Answer 1

Array#reduce

A reasonable alternative to avoid .map followed by .slice() is to use .reduce() to generate the windows:

function toWindows(inputArray, size) { 
  return inputArray
    .reduce((acc, _, index, arr) => {
      if (index+size > arr.length) {
        //we've reached the maximum number of windows, so don't add any more
        return acc;
      }
      
      //add a new window of [currentItem, maxWindowSizeItem)
      return acc.concat(
        //wrap in extra array, otherwise .concat flattens it
        [arr.slice(index, index+size)]
      );
      
    }, [])
}

const input = [1, 2, 3, 4, 5, 6, 7, 8, 9];

//JSON.stringify to produce more compact result in the console
console.log(JSON.stringify(toWindows(input, 2))); 
console.log(JSON.stringify(toWindows(input, 3))); 
console.log(JSON.stringify(toWindows(input, 4)));
console.log(JSON.stringify(toWindows(input, 9)));
console.log(JSON.stringify(toWindows(input, 10)));



//somewhat more realistic usage:
//find the maximimum odd sum when adding together three numbers at a time
const output = toWindows([ 3, 9, 1, 2, 5, 4, 7, 6, 8 ], 3)
  .map(window => window.reduce((a,b) => a+b)) //sum
  .filter(x => x%2 === 1) //get odd
  .reduce((highest, current) => Math.max(highest, current), -Infinity) //find highest
  
console.log(output)

This can then be shortened, if needed:

function toWindows(inputArray, size) { 
  return inputArray
    .reduce(
      (acc, _, index, arr) => (index+size > arr.length) ? acc : acc.concat([arr.slice(index, index+size)]),
      []
    )
}

const input = [1, 2, 3, 4, 5, 6, 7, 8, 9];

//JSON.stringify to produce more compact result in the console
console.log(JSON.stringify(toWindows(input, 2))); 
console.log(JSON.stringify(toWindows(input, 3))); 
console.log(JSON.stringify(toWindows(input, 4)));
console.log(JSON.stringify(toWindows(input, 9)));
console.log(JSON.stringify(toWindows(input, 10)));



//somewhat more realistic usage:
//find the maximimum odd sum when adding together three numbers at a time
const output = toWindows([ 3, 9, 1, 2, 5, 4, 7, 6, 8 ], 3)
  .map(window => window.reduce((a,b) => a+b)) //sum
  .filter(x => x%2 === 1) //get odd
  .reduce((highest, current) => Math.max(highest, current), -Infinity) //find highest
  
console.log(output);

Array.from

The approach can be simplified using Array.from to generate an array with the appropriate length first and then populate it with the generated windows:

function toWindows(inputArray, size) {
  return Array.from(
    {length: inputArray.length - (size - 1)}, //get the appropriate length
    (_, index) => inputArray.slice(index, index+size) //create the windows
  )
}

const input = [1, 2, 3, 4, 5, 6, 7, 8, 9];

//JSON.stringify to produce more compact result in the console
console.log(JSON.stringify(toWindows(input, 2))); 
console.log(JSON.stringify(toWindows(input, 3))); 
console.log(JSON.stringify(toWindows(input, 4)));
console.log(JSON.stringify(toWindows(input, 9)));
console.log(JSON.stringify(toWindows(input, 10)));



//somewhat more realistic usage:
//find the maximimum odd sum when adding together three numbers at a time
const output = toWindows([ 3, 9, 1, 2, 5, 4, 7, 6, 8 ], 3)
  .map(window => window.reduce((a,b) => a+b)) //sum
  .filter(x => x%2 === 1) //get odd
  .reduce((highest, current) => Math.max(highest, current), -Infinity) //find highest
  
console.log(output)

Generator

Another alternative is to use a generator function, instead of pre-computing all windows. This can be useful for more lazy evaluation with a sliding window approach. You can still compute all the windows using Array.from, if needed:

function* windowGenerator(inputArray, size) { 
  for(let index = 0; index+size <= inputArray.length; index++) {
    yield inputArray.slice(index, index+size);
  }
}

function toWindows(inputArray, size) {
  //compute the entire sequence of windows into an array
  return Array.from(windowGenerator(inputArray, size))
}

const input = [1, 2, 3, 4, 5, 6, 7, 8, 9];

//JSON.stringify to produce more compact result in the console
console.log(JSON.stringify(toWindows(input, 2))); 
console.log(JSON.stringify(toWindows(input, 3))); 
console.log(JSON.stringify(toWindows(input, 4)));
console.log(JSON.stringify(toWindows(input, 9)));
console.log(JSON.stringify(toWindows(input, 10)));



//somewhat more realistic usage:
//find the sum closest to a target number when adding three numbers at a time
const veryLargeInput = [17, 95, 27, 30, 32, 38, 37, 67, 53, 46, 33, 36, 79, 14, 19, 25, 3, 54, 98, 11, 68, 96, 89, 71, 34, 31, 28, 13, 99, 10, 15, 84, 48, 29, 74, 78, 8, 90, 50, 49, 59, 18, 12, 40, 22, 80, 42, 21, 73, 43, 70, 100, 1, 44, 56, 5, 6, 75, 51, 64, 58, 85, 91, 83, 24, 20, 72, 26, 88, 66, 77, 60, 81, 35, 69, 93, 86, 4, 92, 9, 39, 76, 41, 37, 63, 45, 61, 97, 2, 16, 57, 65, 87, 94, 52, 82, 62, 55, 7, 23];
const targetNumber = 100;

console.log(`-- finding the closest number to ${targetNumber}`)

const iterator = windowGenerator(veryLargeInput, 3);

let closest = -1;

for (const win of iterator) {
  const sum = win.reduce((a, b) => a+b);
  
  const difference = Math.abs(targetNumber - sum);
  const oldDifference = Math.abs(targetNumber - closest);
  
  console.log(
    `--- evaluating: ${JSON.stringify(win)}
    sum: ${sum},
    difference with ${targetNumber}: ${difference}`
  );
  
  if (difference < oldDifference) {
    console.log(`---- ${sum} is currently the closest`);
    closest = sum;
    
    if (difference === 0) {
      console.log("----- prematurely stopping - we've found the closest number")
      break;
    }
  }
  
}

console.log(`-- closest sum is: ${closest}`)

Answer 2

Have you considered going recursive?

• l is the size of each window
• xs is your list
• i is the number of iterations we need to make which is xs.length - l
• out contains the result

A slice can be obtained with xs.slice(i, i + l). At each recursion i is incremented until i gets to a point where the next slice would contain less than l elements.

const windows = (l, xs, i = 0, out = []) =>
  i > xs.length - l
    ? out
    : windows(l, xs, i + 1, [...out, xs.slice(i, i + l)]);


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

There is also a non-recursive solution with flatMap.

With flatMap you can return an array at each iteration, it will be flattened in the end result:

const duplicate = xs => xs.flatMap(x => [x, x]);
duplicate([1, 2]);
//=> [1, 1, 2, 2]

So you can return your slices (wrapped in []) until i gets over the limit which is xs.length - l:

const windows = (l, xs) =>
  xs.flatMap((_, i) =>
    i <= xs.length - l
      ? [xs.slice(i, i + l)]
      : []);

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

---

Note that in some libraries like ramda.js, this is called aperture:

Returns a new list, composed of n-tuples of consecutive elements. If n is greater than the length of the list, an empty list is returned.

aperture(3, [1,2,3,4,5,6,7,8,9]);
//=> [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7], [6, 7, 8], [7, 8, 9]]

As you can see a few people had the same question before:

• how I can solve aperture function in javascript?
• How to create windowed slice of array in javascript?