Sliding Window Maximum [Code + Interactive Visualization]

Sliding Window Hard

Python Java C++

from collections import deque

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    
    q = deque()  # Stores indices
    res = []
    
    for i in range(len(nums)):
        # Remove elements out of the current window
        if q and q[0] == i - k:
            q.popleft()
        
        # Remove elements smaller than the current element
        while q and nums[q[-1]] < nums[i]:
            q.pop()
        
        q.append(i)
        
        # Add the maximum of the current window to the result
        if i >= k - 1:
            res.append(nums[q[0]])
    
    return res

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Edge case: empty array
        if (nums.length == 0) return new int[]{};
        
        LinkedList q = new LinkedList<>(); // Store indices
        int[] res = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            // Remove elements out of the current window
            if (!q.isEmpty() && q.peekFirst() == i - k) 
                q.poll();
            
            // Remove elements smaller than the current element
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) 
                q.removeLast();
            
            q.offer(i);
            
            // Add the maximum of the current window to the result
            if (i + 1 >= k) 
                res[i - k + 1] = nums[q.peekFirst()];
        }
        
        return res; 
    }
}

#include 
#include 
using namespace std;

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        if (nums.empty()) return {};
        
        deque q; // Store indices
        vector res;
        
        for (int i = 0; i < nums.size(); i++) {
            // Remove elements out of the current window
            if (!q.empty() && q.front() == i - k) 
                q.pop_front();
            
            // Remove elements smaller than the current element
            while (!q.empty() && nums[q.back()] < nums[i]) 
                q.pop_back();
            
            q.push_back(i);
            
            // Add the maximum of the current window to the result
            if (i >= k - 1) 
                res.push_back(nums[q.front()]);
        }
        
        return res;
    }
};

Problem Statement

Given an array `nums` and an integer `k`, return the maximum values of each sliding window of size `k` in the array.

Detailed Explanation

Approach

This solution uses a deque (double-ended queue) to efficiently track the maximum element in the current sliding window. The deque stores indices of elements in the array, ensuring that the front of the deque always holds the index of the current maximum.

Key Concepts

1. Deque: Efficiently tracks maximum values by removing irrelevant elements.
2. Sliding Window: Maintain the window's size and update the deque as elements are added and removed.
3. Indexing: Deque stores indices, allowing access to the values in constant time.

Algorithm Steps

1. Initialize an empty deque and a result list.
2. Iterate through the array:
   • Remove indices of elements that are out of the current window.
   • Remove indices of elements smaller than the current element from the back of the deque.
   • Add the current index to the deque.
   • Add the value of the element at the front of the deque to the result if the window size is met.

Time and Space Complexity

• Time Complexity: O(n)
  • Each element is added and removed from the deque at most once.
• Space Complexity: O(k)
  • The deque holds at most `k` indices at any time.

Why This Works

This solution is efficient because the deque maintains the maximum of the current window in constant time, and elements that can no longer affect the result are removed promptly.

Edge Cases

• Empty array: Return an empty list.
• Window size larger than array: Return an empty list.
• Single element array: Return the single element for any valid window size.

Common Mistakes

• Not handling elements outside the current window correctly.
• Confusing indices and values when updating the deque.
• Forgetting to add the maximum value to the result after processing each window.

Sliding Window Maximum

Array: Window size (k): Start

Deque (indices):

Result:

Next Step