Sliding Window Maximum hard

Problem Statement

You are given an array of integers nums and an integer k. You are asked to find the maximum value within every sliding window of size k as the window slides from left to right across the array. Return the array of maximum values for each window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Example 2:

Input: nums = [1], k = 1 Output: [1]

Steps to Solve:

1. Handle edge cases: If the input array is empty or k is greater than or equal to the array's length, return an empty array. If k is 1, return the input array.

2. Use a Deque: Employ a deque (double-ended queue) to store indices of elements. This deque will maintain indices of the potentially maximum elements within the current window in decreasing order.

3. Sliding Window: Iterate through the array.

4. Deque Maintenance: For each element:

   • Remove elements from the rear of the deque whose indices are outside the current window.
   • Remove elements from the front of the deque that are smaller than the current element. This ensures that the deque only contains indices of elements that are potentially maximums.
   • Add the current element's index to the rear of the deque.

5. Result: The element at the front of the deque always represents the maximum value within the current window. Add this maximum to the result array.

Explanation:

The deque maintains a strictly decreasing order of elements. This ensures that the largest element within the window is always at the front. By removing smaller elements from the front and elements outside the window from the rear, we efficiently track the maximum element within the sliding window.

Code (TypeScript):

function maxSlidingWindow(nums: number[], k: number): number[] {
    if (nums.length === 0 || k >= nums.length) return [];
    if (k === 1) return nums;

    const result: number[] = [];
    const deque: number[] = []; // Deque to store indices

    for (let i = 0; i < nums.length; i++) {
        // Remove elements outside the window from the rear
        while (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }

        // Remove smaller elements from the front
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }

        // Add current element's index to the rear
        deque.push(i);

        // Add maximum to result if window is full
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

Complexity:

• Time Complexity: O(N), where N is the length of the input array. Each element is processed at most twice (once added to the deque and once removed).
• Space Complexity: O(k), where k is the size of the window. The deque's size is at most k.