Find Maximum in a sliding window

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

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

Constraints:

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

Test Cases

Sample Example 1

Input:

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

Output: 236

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: 45678910

*Naive Solution Easiest solution I can think right now is If I create a Function that gives me largest value of an array then I can pass all the window_size arrays and store there result.

TC: O(N·K)

SC: O(N)

Optimized Solutiion

Another way of solving this problem I could think is If I use a data structure like queue and keep storing index of number, Intention is I want largest value stays at bottom If at any point I see value that is larger then largest value current I'll pop out all other values and store the largest one. In queue I will not store number instead I'll prefer to store their index this will help me keep track of current index and element that are not part of current window.

Before storing any value in queue I'll perform a cleanup operation. This cleanup will remove all the values smaller the current value and then we can store it.

For first k elements we'll first find largest number and store its result explicitly and then for remaining elements we'll handle out of current_window case.

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));