Sliding Window Maximum

Problem Statement:

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.

Constraints: 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length

Solution:

0. Brute Force Approach:

Calculate the maximum for each sliding window by iterating through each window and finding the maximum element within that window. TC: O((n− k + 1) × k) SC: O(n−k+1) for the result array.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
 
        int n = nums.length;
        int[] result = new int[n - k + 1];
 
        for (int i = 0; i <= n - k; i++) {
            int max = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }
            }
            result[i] = max;
        }
 
        return result;
    }
}

1. Next Greater Element Approach:

Caution

In getNextGreaterElements() function, we’ll initialize nge’s array with ‘n’, to be used as a boundary marker. This is done so that in while (nge[end] <= windowSize), end never crosses the bound of nge array.

TC: O(n) SC: O(n)

import java.util.*;
 
class Solution {
	
    private int[] getNextGreaterElements(int[] nums, int n) {
        int[] nge = new int[n]; // Next Greater Element array
        Arrays.fill(nge, n); // * * * Initialize NGE array with n (size of nums) * * *
        Stack<Integer> stack = new Stack<>();
 
        // Calculate Next Greater Element for each position
        for (int end = n - 1; end >= 0; end--) {
            // tab tak pop karo jabtak us se bade element ka index na mil jaye
            while (!stack.isEmpty() && nums[end] >= nums[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                nge[end] = stack.peek();
            }
            stack.push(end);
        }
 
        return nge;
    }
 
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
		
		//Get the next greater elements indexes.
        int[] nge = getNextGreaterElements(nums, n);
        int[] result = new int[n - k + 1];
        
        int start = 0;
        int end = 0;
        
        // Find maximum for each sliding window
        while (start < n - k + 1) {
            // Ensure "end" is within the current window and everytime "end" is
            // left behind bring it to "start"
            // Ensure "end" is within the current window and sync with "start"
            if (end < start) {
                end = start;
            }
 
            // Move "end" to the position of the next greater element within the current window
            int windowSize = start + k - 1;
            while (nge[end] <= windowSize) {
                end = nge[end];
            }
 
            // Now, end will be the max of curr window
            // Add the maximum element of the current window to the result
            result[start] = nums[end];
            start++;
        }
 
        return result;
    }
}
 

2. Monotonic Queue Approach:

TC: O(n) SC: O(n)

Info

• The front of the deque always holds the index of the maximum element for the current window. By maintaining the deque in descending order, we ensure that the maximum value of the current window is always at the front, allowing us to retrieve it in constant time O(1).

import java.util.Deque;
import java.util.LinkedList;
 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }
 
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // Stores indices of array elements
        int end = 0;
 
        while (end < n) {
            // Remove elements from the front of the deque if they are out of the window
            int windowSize = end - k + 1;
            if (!deque.isEmpty() && deque.peek() < windowSize) {
                deque.poll();
            }
 
            // Remove elements from the back of the deque if they are smaller than the current element to maintain the
            // decreasing order
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[end]) {
                deque.pollLast();
            }
 
            // Add the current element at the back of the deque
            deque.offer(end);
 
            // The front of the deque is the maximum element in the current window
            if (windowSize >= 0) {
                result[windowSize] = nums[deque.peek()];
            }
 
            end++; // Expand the window by moving the end pointer
        }
 
        return result; // Return the array of maximum values
    }
}