20. Sliding Window Maximum · DSA Practice

A window of size k slides from the left of nums to the right, one step at a time. Return the maximum of each window position.

Example 1

Input: nums = [4,2,12,3,8,1,5], k = 3

Output: [12,12,12,8,8]

Explanation: Windows: [4,2,12] [2,12,3] [12,3,8] [3,8,1] [8,1,5].

Example 2

Input: nums = [9,8,7,6], k = 2

Output: [9,8,7]

Hint 1

Keep a deque of indices whose values are in decreasing order.

Hint 2

The front of the deque is always the window maximum.

Sliding WindowMonotonic QueueDeque

Approach 1: Scan each window

Find the max of every window directly.

⏱ Time O(n · k)💾 Space O(1)

Approach 2: Max-heap

Push (value, index); pop stale tops.

⏱ Time O(n log n)💾 Space O(n)

Approach 3: Monotonic deque ✅

Each index is pushed and popped at most once.

⏱ Time O(n)💾 Space O(k)

Reference solution for Monotonic deque (time O(n), space O(k)). Each solution passes every test in all four languages.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()            # indices; their values are decreasing
        res = []
        for i, x in enumerate(nums):
            while dq and nums[dq[-1]] <= x:
                dq.pop()        # smaller values can never be a maximum again
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()    # front slid out of the window
            if i >= k - 1:
                res.append(nums[dq[0]])
        return res

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();   // indices with decreasing values
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst();
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;                            // indices with decreasing values
        vector<int> res;
        for (int i = 0; i < (int)nums.size(); i++) {
            while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
            dq.push_back(i);
            if (dq.front() <= i - k) dq.pop_front();
            if (i >= k - 1) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};

function maxSlidingWindow(nums, k) {
  const dq = []; let head = 0; // dq[head..] holds indices with decreasing values
  const res = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (dq[head] <= i - k) head++;
    if (i >= k - 1) res.push(nums[dq[head]]);
  }
  return res;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Sliding Window.