Sliding Window Maximum

Level - Hard

Statement

Given an array nums of integers and a window size k, slide the window from left to right through the array and return an array result consisting of the maximum value in each window of size k. If the array is empty or the window size is greater than the length of the array, return an empty array.

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

You can try this at:

• https://leetcode.com/problems/sliding-window-maximum/

Brute-Force Method

• in this method we will loop through all the windows and track maximum in following windows
• so if n is the size of the array and k is the window size then n-k+1 windows are there
• in inner loop track the max element in that window

Java

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int index = 0;
    int[] res = new int[n-k+1];
    for(int i=0;i<=n-k;i++){
        int maxi = Integer.MIN_VALUE;
        for(int j=i;j<=i+k-1;j++){
            maxi = Math.max(maxi,nums[j]);
        }
        res[index] = maxi;
        index++;
    }
    return res;
}

Python

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        result = []
        window = deque()

        for i in range(n):
            # Remove elements outside the current window
            while window and window[0] <= i - k:
                window.popleft()

            # Remove smaller elements from the right side of the window
            while window and nums[window[-1]] <= nums[i]:
                window.pop()

            window.append(i)

            # Process the maximum element within the window
            if i >= k - 1:
                result.append(nums[window[0]])

        return result

CPP

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        int index = 0;
        vector<int> res(n - k + 1);
        deque<int> window;

        for (int i = 0; i < n; i++) {
            // Remove elements outside the current window
            while (!window.empty() && window.front() <= i - k) {
                window.pop_front();
            }

            // Remove smaller elements from the right side of the window
            while (!window.empty() && nums[window.back()] <= nums[i]) {
                window.pop_back();
            }

            window.push_back(i);

            // Process the maximum element within the window
            if (i >= k - 1) {
                res[index++] = nums[window.front()];
            }
        }

        return res;
    }
};

Time Complexity:

O(N^2)

Space Complexity:

O(1)

Optimal Approach

Optimal Approach Algorithm

1. Initialize an empty deque dq to store the indices of the elements in the current window.
2. Initialize an empty array result to store the maximum value in each window.
3. Iterate through the elements in nums:
   • check whether the first element in dq is still present in window using:

     while(!dq.isEmpty() && i-k>=dq.getFirst()) dq.removeFirst();
   • we have to maintain the monotonic queue(so first element is maximum and last element is minimum) using:

     while(!dq.isEmpty() && nums[dq.getLast()] < nums[i]) dq.removeLast();
   • Add the current index to the back of dq.
   • check whether we have processed elements equals to or more than window size using:

     if(i>=k-1) result[index++] = nums[dq.getFirst()];

The key idea behind this approach is to maintain a monotonic queue that stores the indices of the elements in the current window, in decreasing order of their values. The maximum element in the current window is always at the front of the queue.

Java

class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n-k+1];
        int index = 0;
        
        // deque for maintaining max element in window - storing index 
        Deque<Integer> dq = new LinkedList<>();
        for(int i=0;i<n;i++){
            // maintain at most k elements in queue
            while(!dq.isEmpty() && i-k>=dq.getFirst()) dq.removeFirst();
            
            // so we have to maintain large element in window at front
            while(!dq.isEmpty() && nums[dq.getLast()] < nums[i]) dq.removeLast();

            // add the current element index
            dq.add(i);
            // if completed the first window add into the result
            if(i>=k-1) result[index++] = nums[dq.getFirst()];
        }
        return result;
    }
}

CPP

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result(n - k + 1);
        int index = 0;
        deque<int> dq;

        for (int i = 0; i < n; i++) {
            // Maintain at most k elements in the deque
            while (!dq.empty() && i - k >= dq.front()) {
                dq.pop_front();
            }

            // Maintain larger elements in the window at the front of the deque
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            // Add the maximum element to the result when the window is complete
            if (i >= k - 1) {
                result[index++] = nums[dq.front()];
            }
        }

        return result;
    }
}

Python

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        result = []
        index = 0
        dq = deque()

        for i in range(n):
            # Maintain at most k elements in the deque
            while dq and i - k >= dq[0]:
                dq.popleft()

            # Maintain larger elements in the window at the front of the deque
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            dq.append(i)

            # Add the maximum element to the result when the window is complete
            if i >= k - 1:
                result.append(nums[dq[0]])

        return result

Complexity

Time Complexity: O(N)+O(N) ~ O(N)

Space Complexity: O(K)