# Find Maximum in Sliding Window 

[Link](https://www.educative.io/module/lesson/data-structures-in-javascript/gxnlB9N5MR9)


## Description

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

  Let's try to find all maximums for `w = 3`:

    [-4, 2, -5, 3, 6]

  **Step 1:** for the first *3* elements, max is 2.

    [-4, 2, -5], 3, 6
         *

  **Step 2:** Slide `window` one position to right and the max is now *3*

    -4, [2, -5, 3], 6
                *

  **Step 3:** In the last `window` the max is 6.

    -4, 2, [-5, 3, 6]

## Solution

```
let ffindMaxSlidingWindow = function(arr, windowSize) {
  let result = []

  if (arr.length == 0){
    return result;
  }

  if (windowSize > arr.length) {
    return result;
  }

  let window_ = 0;
  // find max for first window
  for (let i = 0; i < windowSize; i++) {
    while(window_.length > 0 && arr[i] >= arr[window_[window_.length - 1]]){
      window_.pop();
    }
    window.push(i);
  }

  result.push(arr[window_[0]])

  for (let i = windowSize; i < arr.length; i++){
    // remove all numbers that are smaller than the current max from the list
    while (window_.length > 0 && arr[i] >= arr[window_[window_.length -1]]) {
      window_.pop();
    }
    // remove first number if it doesn't fall in window
    if (window_.length > 0 && (window_[0] <= i - windowSize>)){
      window_.shift();
    }
    window_.push(i)
    result.push(arr[window_[0]])
  }
  return result;
}

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log("Array = " + array);
console.log("Max = " + ffindMaxSlidingWindow(array, 3));
// Max = 3,4,5,6,7,8,9,10

let array1 = [10, 6, 9, -3, 23, -1, 34, 56, 67, -1, -4, -8, -2, 9, 10, 34, 67]
console.log("Array = " + array1);
console.log("Max = " + ffindMaxSlidingWindow(array1, 3))
// Max = 10,9,23,23,34,56,67,67,67,-1,-2,9,10,34,67
```

### Runtime Complexity

The runtime complexity in *`linear, O(n)`*.

> Every element is pushed and popped from the deque only once in a single traversal.

### Memory Complexity

Memory complexity is *`linear, O*(w)`*, where `w` is the window size