Code Logo

Sliding Window Maximum

Published at25 Jul 2026
Created by
Hard 0 views
Like0

Given an array of integers nums and an integer k, find the maximum element in every contiguous subarray of size k. Return an array containing these maximum values in order.

The naive approach checks all k elements for each window, resulting in O(n*k) time. The optimal solution uses a deque (double-ended queue) that stores indices of elements in decreasing order of their values. The front of the deque always holds the index of the maximum element for the current window.

As we slide the window from left to right, we perform three operations for each new element: remove indices that are outside the current window from the front, remove indices of elements smaller than the current element from the back (they can never be maximum for this or any future window), and add the current index to the back. The element at the front of the deque is the maximum for the current window.

This deque approach achieves O(n) time complexity because each index is added to and removed from the deque at most once. Space complexity is O(k) for the deque. This problem is a classic example where a monotonic deque enables an efficient sliding window solution that would otherwise require O(n*k) time with a brute-force approach.

Edge cases include k=1 where each element is its own window maximum, k equal to the array length where there is exactly one window, and arrays smaller than k (return an empty array).

Example Input & Output

Example 1
Input
[7,2,4],2
Output
[7,4]
Explanation

First window max=7, second max=4

Example 2
Input
[1,3,-1,-3,5,3,6,7],3
Output
[3,3,5,5,6,7]
Explanation

Window max values at each position: [3],[3,5],[5,5,6],[5,6,7]...

Example 3
Input
[5,4,3,2,1],3
Output
[5,4,3]
Explanation

Decreasing sequence

Example 4
Input
[1,-1],1
Output
[1,-1]
Explanation

Each element is its own window max

Example 5
Input
[1],1
Output
[1]
Explanation

Single element window

Algorithm Flow

Recommendation Algorithm Flow for Sliding Window Maximum
Recommendation Algorithm Flow for Sliding Window Maximum

Solution Approach

Given an array nums and a sliding window of size k, return the maximum element in each window. Use a deque that stores indices of elements in decreasing order. For each new element, remove indices outside the window from the front, and remove indices of smaller elements from the back. The front of the deque always holds the index of the maximum for the current window.

function maxSlidingWindow(nums, k) {
  var result = [], deque = [];
  for (var i = 0; i < nums.length; i++) {
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

The deque maintains candidates for the maximum in decreasing value order. When the window slides, expired indices are removed from the front. New elements remove smaller values from the back, ensuring the deque stays sorted descending. The front element is always the current window's maximum.

Time complexity is O(n), space complexity is O(k) for the deque.

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[]{};
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        int ri = 0;
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) res[ri++] = nums[dq.peekFirst()];
        }
        return res;
    }
}