So I’m trying to stay true to my resolution, write one or more article about algorithms and datastructure everyday to refresh my memory on how everything works.

Description

Given a large array of integers and a window of size ‘w’, find the current maximum in the window as the window slides through the entire array.

Example

Consider the array below and let’s try to find all maximum with window size = 3, for explanation let’s start with a smaller array so we can go over each steps.

[-1 2 -2 5 9]

• For the first window size (3) elements, the max is 2
• Slide window one position right and then the max element is 5
• Slide window one position right again, and then the max element is 9

Solutions

Algorithm

• Check if the window size is bigger than the array it self, and if so return
• Find the max for the first window, by storing the max value into a window
• Push the first element of the window into the results array
• Iterate the rest of the elements ** Remove all the elements from the tail of the window that are equal or smaller than the current element ** Remove the element in the head if the index no longer is in the current window ** Push the current element into the window ** Current max is at the head of the array and can be pushed in results

Iterative solution

Runtime complexity

Linear, О(nlogw)

Memory complexity

Logarithmic, О(w)

The reason why it has O(logn) memory complexity is because it will have to consume memory on the stack.

Implementation

let find_max_sliding_window = function(arr, window_size) {
  let result = [];
  if (window_size > arr.length) {
    return [];
  }

  let wind = [];
  for (let i = 0; i < window_size; i++) {
    while (wind.length > 0 && arr[i] >= arr[wind[wind.length - 1]]) {
      wind.pop(); // remove the element of the window
    }
    wind.push(i); // put the index of the element that has max in the window
  }

  result.push(arr[wind[0]]);

  // move the window to the right side and go over the window again
  for (let i = window_size; i < arr.length; i++) {
    while (wind.length > 0 && arr[i] >= arr[wind[wind.length - 1]]) {
      wind.pop(); // remove the element of the window
    }
    // move the element to right and remove the first element in the window
    if (wind.length > 0 && (wind[0] <= i - window_size)) {
      wind.shift();
    }
    wind.push(i);
    result.push(arr[wind[0]]);
  }

  return result;
};

console.log(find_max_sliding_window([97, 7, 36, 16, 90, 54, 54, 81, 43, 66, 72, 97, 68, 27, 12, 83, 8, 26, 70, 8], 2));
console.log(find_max_sliding_window([97, 7, 36, 16, 90, 54, 54, 81, 43, 66, 72, 97, 68, 27, 12, 83, 8, 26, 70, 8], 3));
console.log(find_max_sliding_window([97, 7, 36, 16, 90, 54, 54, 81, 43, 66, 72, 97, 68, 27, 12, 83, 8, 26, 70, 8], 4));
console.log(find_max_sliding_window([97, 7, 36, 16, 90, 54, 54, 81, 43, 66, 72, 97, 68, 27, 12, 83, 8, 26, 70, 8], 5));

After running the application the output is

[97, 36, 36, 90, 90, 54, 81, 81, 66, 72, 97, 97, 68, 27, 83, 83, 26, 70, 70]
[97, 36, 90, 90, 90, 81, 81, 81, 72, 97, 97, 97, 68, 83, 83, 83, 70, 70]
[97, 90, 90, 90, 90, 81, 81, 81, 97, 97, 97, 97, 83, 83, 83, 83, 70]
[97, 90, 90, 90, 90, 81, 81, 97, 97, 97, 97, 97, 83, 83, 83, 83]

This was quite easy but we have to wrap our heads around how we would approach this, if we remember that do we really need to store all the elements in memory, and how can we create an efficient structure that can store the data for us.