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?

"better solution" better in what sense? Also if the code works the question is better suited to https://codereview.stackexchange.com/ — Yury Tarabanko, Jul 12 '19 at 07:39
I'm voting to close this question as off-topic because the question belongs to https://codereview.stackexchange.com/ — Yury Tarabanko, Jul 12 '19 at 07:39
I need a short, best-practice solution for this common problem that can serve as reference for future applications. — Jens Jensen, Jul 12 '19 at 07:52
For cross-reference: https://stackoverflow.com/questions/52219405/how-to-create-windowed-slice-of-array-in-javascript — Jens Jensen, Mar 18 '20 at 12:03

VLAZ · Answer 1 · 2020-10-20T11:55:16.070

`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}`)

score 3 · Answer 2 · edited Sep 07 '21 at 16:32

Adding to the native JavaScript objects through their prototype is not a good idea. This can break things in unexpected ways and will cause a lot of frustration for you and anyone else using your code. It is better to just create your own function in this case.

To get the functionality you want, you could simply pass the array to your function and then access it from there. Make the method calls you want on the array from your function. Following the principle of KISS, there's no need for anything more fancy here.

Also, remember that Array.map is called for each element of the array. That's not really what you need here. If the goal is to get a sliding window of size n, and you want each of the windows to be added to a new array, you could use a function like this:

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

const slicingWindows = (arr, size) => {
    if (size > arr.length) {
        return arr;
    }
    let result = [];
    let lastWindow = arr.length - size;
    for (let i = 0; i <= lastWindow; i += 1) {
        result.push(arr.slice(i, i + size));
    }
    return result;
};

So here, we will get an array of windows, which are also arrays. Calling console.log(slicingWindows(a,3)), gives this output:

[1, 2, 3]
[3, 4, 5]
[4, 5, 6]
[5, 6, 7]
[6, 7, 8]

I changed the example because it confused the sliding window problem with my convenience of calling it as Array.prototype function. — Jens Jensen, Jul 12 '19 at 07:19
Your example output shows *slicing*, not sliding windows. I updated the question for clarification. Also your example code seems to produce empty arrays only. — Jens Jensen, Jul 25 '19 at 12:08

customcommander · Answer 3 · 2019-12-16T22:11:56.620

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:

Ivan Hristov · Answer 4 · 2019-09-30T16:35:39.910

Using JS ES6, you can do the following:

class SlidingWindow{
  constructor(windowSize) {
    this.deque = []; // for storing the indexex of the 'k' elements in the input 
    this.windowSize = windowSize;
  }

  compute(input){   
    let output = [];

    if(!input || input.length === 0) {
        return [];
    }

    if(input.length < this.windowSize) {
        return input;
    }

    for(let i=0; i < input.length; i++) {
        
        //if the index in the first element of the this.deque is out of bound (i.e. idx <= i-this.windowSize) then remove it
        if(this.deque.length > 0 && this.deque[0] === i-this.windowSize) {
            this.deque.shift(); //remove the first element
        }
                
        this.deque.push(i)
        
        if(i+1 >= this.windowSize) {
            output.push(this.deque.map(idx => input[idx]));
        }
    }
    return output;
  }
}

//Here is how to use it:
let slidingWindow = new SlidingWindow(3);

console.log('computed sliding windows: '+JSON.stringify(slidingWindow.compute([1,2,3,4,5,6,7,8,9])));

To compute the maximum of each sliding window, you can customise the above code as follows:

class SlidingWindow{
  constructor(windowSize) {
    this.deque = []; // for storing the indexex of the 'k' elements in the input 
    this.windowSize = windowSize;
  }

  customCompute(input, processWindow, addOutput) {
    let output = [];

    if(!input || input.length === 0) {
        return [];
    }

    if(input.length < this.windowSize) {
        return input;
    }

    for(let i=0; i < input.length; i++) {
        
        //if the index in the first element of the this.deque is out of bound (i.e. idx <= i-this.windowSize) then remove it
        if(this.deque.length > 0 && this.deque[0] === i-this.windowSize) {
            this.deque.shift(); //remove the first element
        }

        processWindow(this.deque, input[i], input)

        this.deque.push(i)
        
        if(i+1 >= this.windowSize) {
            output.push(addOutput(this.deque, input));
        }
    }
    this.deque = [];
    return output;
  }
}

let slidingWindow = new SlidingWindow(3);

console.log('computed sliding windows: '+JSON.stringify(slidingWindow.compute([1,2,3,4,5,6,7,8,9])));

function processWindow(deque, currentElement, input){
  while(deque.length > 0 && currentElement > input[deque[deque.length -1]]) {
            deque.pop(); //remove the last element
        }
};
console.log('computed sliding windows maximum: '+JSON.stringify(slidingWindow.customCompute([1,3,-1,-3,5,3,6,7], processWindow, (deque, input) => input[deque[0]])));

Hi Ivan, thanks for your lengthy attempt. Could you please elaborate in which respects you consider it better than the 1-liner mentioned in the question? — Jens Jensen, Oct 02 '19 at 09:33
Hi @JensJensen, I would highlight two aspects: 1. readability 2. flexibility - with this solution you can execute different logic in different scenarios. — Ivan Hristov, Oct 02 '19 at 14:07

Abshir · Answer 5 · 2021-12-16T21:12:25.950

Simple while-loop solution

function windowArray(array, windowSize) {
  return array.map((value, index) => {
    const windowedArray = [];
    while (array[index] && windowedArray.length < windowSize) {
      windowedArray.push(array[index]);
      index++;
    }
    return windowedArray;
  });
};

const array = [1, 1, 1, 2, 2, 2, 3, 3, 3]
const windowValue = 3;
const windowedArray = windowArray(array, windowValue)
const filteredWindowedArray = windowedArray.filter(group => group.length === windowValue);

console.log("INPUT ARRAY", JSON.stringify(array))
console.log("WINDOWED ARRAY", JSON.stringify(windowedArray));
console.log("FILTERED WINDOWED ARRAY", JSON.stringify(filteredWindowedArray));

Sliding window over Array in JavaScript

5 Answers5

`Array#reduce`

`Array.from`

Generator

Linked