Sliding Window Maximum hard

Problem Statement

Given an array nums and an integer k, return the maximum value in each sliding window of size k. A sliding window is a contiguous subarray of size k that moves from left to right by one position each time.

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

1. Initialization: Create a deque (double-ended queue) to store indices of elements. This deque will maintain the indices of potential maximums in the current window.

2. Sliding Window: Iterate through the nums array.

3. Deque Maintenance: For each element nums[i]:

   • Remove elements from the rear of the deque whose indices are smaller than i - k (elements outside the current window).
   • Remove elements from the rear of the deque that are smaller than the current element nums[i]. These elements cannot be the maximum in any future window.
   • Add the current element's index i to the rear of the deque.

4. Result: The front element of the deque always represents the index of the maximum element in the current window. Add nums[deque.getFirst()] to the result list.

5. Return: Return the result list containing the maximums of each sliding window.

Explanation

The deque acts as a "monotonic decreasing queue". It ensures that the elements are stored in descending order of their values. This allows us to quickly find the maximum element in the current window by simply looking at the front of the deque. Removing elements from the rear that are smaller than the current element guarantees that we only keep potentially maximum elements. Removing elements from the front that are outside the current window maintains the window's size constraint. This approach ensures that we efficiently compute the maximum within each window in O(n) time.

Code

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Arrays;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Remove elements outside the window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller elements from the rear
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // Add current element's index
            deque.offerLast(i);

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

        return result;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. Each element is added and removed from the deque at most once.
• Space Complexity: O(k), where k is the size of the window. The deque can store at most k elements.