239. Sliding Window Maximum

Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding 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]

Constraints:

• 1 <= nums.length <= 10<sup>5</sup>

• -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

• 1 <= k <= nums.length

Solution

Brute Force Approach

We examine each element and check the next ( k ) elements (including the current one) to find the maximum value, which we then place in the answer array. The size of the answer array is ( n - k + 1 ), where ( n ) is the size of the given array and ( k ) is the window size. We add 1 because if ( k ) equals ( n ), then the entire array is considered one window.

Time - O(n*k)

Space - O(1)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length-k+1];

        for(int i=0; i<nums.length-k+1; i++){
            int max = nums[i];
            for(int j=i; j<i+k; j++){
                max = Math.max(max,nums[j]);
            }
            ans[i] = max;
        }
        return ans;
    }
}

Optimal Approach

In this approach, we merge the concepts of a monotonic stack and a queue to eliminate the need for ( k ) iterations for each index. We use a queue with a size equal to the window (( k )). The main idea is that as the window shifts to the next element, we add the new element to the end of the queue and remove the first element from the front. We also need to maintain the current maximum element for the given window within the queue. There are two options: store the current maximum at the front or the back. Storing it at the back would require discarding incoming elements for the next window, which would disrupt the sequence. Therefore, storing it at the front is optimal.

We achieve this by using the concept of a monotonic stack. The queue can function as a stack, storing only greater values. If an incoming value is smaller than the top, it is pushed (added to the end of the queue). If the incoming value is greater than the top, the top elements are popped until a greater element is found, or the stack is empty, at which point the new value is stored. This ensures the stack is monotonically decreasing from bottom to top, with the maximum element at the bottom or front of the queue.

To handle additions and removals from both ends, we use a double-ended queue (Deque). In Java, the ArrayDeque class provides this functionality. (link)

Time - O(n)

Space - O(k)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        int[] ans = new int[nums.length-k+1];
        for(int i=0; i<nums.length; i++){
            if(!dq.isEmpty() && dq.getFirst()<=(i-k)){
                dq.removeFirst();
            }

            while(!dq.isEmpty() && nums[dq.getLast()]<=nums[i]){
                dq.removeLast();
            }

            dq.addLast(i);
            if(i>=k-1) ans[i-k+1] = nums[dq.getFirst()];
        }

        return ans;
    }
}