Code Implementation

from collections import deque

def maxSlidingWindow(nums, k):
    result = []
    dq = deque()  # stores indices

    for i, num in enumerate(nums):
        # Remove indices that are out of the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove indices whose corresponding values are less than num
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        # The window has formed
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result
      

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

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // stores indices

    for (int i = 0; i < nums.size(); ++i) {
        // Remove indices that are out of the window
        if (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();
        // Remove indices whose corresponding values are less than nums[i]
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}
      

import java.util.*;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // Remove indices out of window
            if (!dq.isEmpty() && dq.peek() < i - k + 1)
                dq.poll();
            // Remove indices whose values are less than nums[i]
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
                dq.pollLast();
            dq.offer(i);
            if (i >= k - 1)
                result[i - k + 1] = nums[dq.peek()];
        }
        return result;
    }
}
      

function maxSlidingWindow(nums, k) {
    const result = [];
    const dq = []; // stores indices

    for (let i = 0; i < nums.length; i++) {
        // Remove indices that are out of the window
        if (dq.length && dq[0] < i - k + 1)
            dq.shift();
        // Remove indices whose corresponding values are less than nums[i]
        while (dq.length && nums[dq[dq.length - 1]] < nums[i])
            dq.pop();
        dq.push(i);
        if (i >= k - 1)
            result.push(nums[dq[0]]);
    }
    return result;
}
      

Problem Description

Given an array of integers nums and an integer k, you are asked to find the maximum value in every contiguous subarray (window) of size k. The output should be a list of these maximums, in the order the windows appear from left to right.

• Each window consists of k consecutive elements from nums.
• For each window, you must report the largest element within that window.
• The solution should be efficient, ideally better than the naive brute-force approach.
• Constraints: 1 <= k <= nums.length, nums.length can be up to 10⁵.

Thought Process

The most straightforward way to solve this problem is to look at every window of size k and find the maximum by scanning all k elements in that window. However, with large arrays and windows, this brute-force method is too slow.

To optimize, we need a way to "slide" the window efficiently and reuse work from previous steps. The key insight is that some elements will never be the maximum in any future window, so we can discard them early. We want a data structure that can quickly add new elements, remove old ones, and always tell us the current maximum.

A double-ended queue (deque) is a perfect fit: it can efficiently add/remove elements from both ends, and we can maintain it so that its front always holds the index of the maximum value in the current window.

Solution Approach

We use a deque to keep track of indices of useful elements in the current window, always in decreasing order of their corresponding values. Here's the step-by-step process:

1. Iterate through the array, processing each element one by one.
2. For each new element at index i:
   • Remove indices from the front of the deque if they are outside the current window (i - k + 1).
   • Remove indices from the back of the deque as long as the value at those indices is less than the current value, since they can never be maximum in this or any future window that includes i.
   • Add the current index i to the back of the deque.
3. Once we've processed at least k elements (i.e., i >= k - 1), the front of the deque contains the index of the maximum value for the current window. We record nums[deque[0]] as the result for this window.
4. Continue until the end of the array.

This approach ensures that each element is added and removed from the deque at most once, giving us an efficient solution.

Example Walkthrough

Let's walk through an example:

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

1. Window 1: [1, 3, -1]
   - Add 1 (index 0), add 3 (index 1, removes 1 since 3 > 1), add -1 (index 2).
   - Deque: [1, 2] (indices).
   - Max is nums[1] = 3.
2. Window 2: [3, -1, -3]
   - Remove indices out of window (none).
   - Add -3 (index 3), no removal since -3 < -1.
   - Deque: [1, 2, 3].
   - Max is nums[1] = 3.
3. Window 3: [-1, -3, 5]
   - Remove index 1 (out of window).
   - Add 5 (index 4), remove -3 and -1 since 5 is greater.
   - Deque: [4].
   - Max is nums[4] = 5.
4. Window 4: [-3, 5, 3]
   - Add 3 (index 5), no removal.
   - Deque: [4, 5].
   - Max is nums[4] = 5.
5. Window 5: [5, 3, 6]
   - Remove index 4 (out of window).
   - Add 6 (index 6), remove 3 and 5 since 6 is greater.
   - Deque: [6].
   - Max is nums[6] = 6.
6. Window 6: [3, 6, 7]
   - Add 7 (index 7), remove 6 since 7 is greater.
   - Deque: [7].
   - Max is nums[7] = 7.

Final Output: [3, 3, 5, 5, 6, 7]

Time and Space Complexity

• Brute-force approach: For each window, scan k elements, for n - k + 1 windows. This is O(nk) time and O(n - k + 1) space for the output.
• Optimized deque approach: Each element is added and removed from the deque at most once, so all deque operations are O(n) time. Space is O(k) for the deque plus O(n - k + 1) for the output.

This makes the deque approach highly efficient for large arrays and windows.

Summary

The Sliding Window Maximum problem is best solved with a deque, which allows us to efficiently keep track of potential maxima as the window slides. By always maintaining the deque in decreasing order and quickly discarding elements that can't contribute to future maxima, we achieve an elegant and efficient O(n) solution. This approach is both practical for large datasets and demonstrates the power of combining data structures with algorithmic insight.