Find Maximum in a sliding window

Given an integer list, nums, find the maximum values in all the contiguous subarrays (windows) of size w.

Given an integer list, nums, find the maximum values in all the contiguous subarrays (windows) of size w.

Sliding Window Maximum

Note: If the window size is greater than the array size, we treat the entire array as a single window.

Constraints

• 1 ≤ arr.length ≤ 10³
• −10⁴ ≤ arr[i] ≤ 10⁴
• 1 ≤ w

Test Cases

Sample Example 1

Input:

• nums = [-4, 2, -5, 3, 6]
• window size = 3

Output: [2, 3, 6]

Sample Example 2

Input:

• nums = [1, 2, 3, 4, 5, 6]
• window size = 6

Output: [6]

Sample Example 3

Input:

• nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
• window size = 4

Output: [4, 5, 6, 7, 8, 9, 10]

Naive Solution

The simplest way to solve this is to write a function that finds the largest value in an array. Then, we run this function on every window of size w in the array, and store each result.

• Time Complexity: O(N·K)
• Space Complexity: O(N)

This works, but it can be slow when the array or window size is large, since we scan the whole window every single time.

Optimized Solution

A faster way to solve this problem uses a queue that stores indices instead of values.

The main idea:

• We want the largest value to always stay at the front of the queue.
• If we come across a new value that is larger than the values already in the queue, we remove those smaller values first. This keeps only useful, still-relevant values in the queue.
• We store indices, not raw values. This way, we can tell which values have fallen outside the current window and remove them too.

Steps

• Before adding any new value to the queue, we do a cleanup. This removes all values from the back of the queue that are smaller than the current value, since they can never be the maximum again.
• For the first w elements, we build the first window. We find its maximum and store it directly.
• For all the remaining elements, we:
  • Clean up smaller values from the back, like before.
  • Check if the front of the queue has fallen out of the current window. If so, we remove it.
  • Add the current index to the queue.
  • The front of the queue now gives us the maximum for this window.

Code

function cleanUp(currentWindow, i, arr) {
  let curr = arr[i];
  while (currentWindow.length !== 0 && curr >= arr[currentWindow[currentWindow.length - 1]]) {
    currentWindow.pop();
  }
}

function largestNumber(arr, k) {
  let result = [];
  let currentWindow = []; // stores indices, front is always the max of the current window

  // Build the first window using the first k elements
  for (let i = 0; i < k; i++) {
    cleanUp(currentWindow, i, arr);
    currentWindow.push(i);
  }
  result.push(arr[currentWindow[0]]);

  // Slide the window across the rest of the array
  for (let i = k; i < arr.length; i++) {
    cleanUp(currentWindow, i, arr);

    // Remove the front index if it has fallen out of the current window
    if (currentWindow.length !== 0 && currentWindow[0] < i - k + 1) {
      currentWindow.shift();
    }

    currentWindow.push(i);
    result[i - k + 1] = arr[currentWindow[0]];
  }

  return result;
}

console.log(largestNumber([-4, 2, -5, 3, 6], 3));