Sliding Window Maximum

Hardsliding-windowdequearraymonotonic-queue
Category: Sliding Window
Companies that ask this question:
AmazonGoogleFacebookMicrosoft
LeetCode →NeetCode →

Approach

Sliding Window Maximum

Problem Statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Examples

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

Example 2

Input: nums = [1], k = 1
Output: [1]

Intuition

Brute force: For each window, scan k elements to find max - O(nk) time.

Optimal: Use a Monotonic Decreasing Deque to track potential maximums:

  • Front of deque always contains index of current maximum
  • Maintain decreasing order (remove smaller elements from back)
  • Remove indices outside window from front

Pattern Recognition

This is a Sliding Window + Monotonic Deque problem:

  • Fixed window size
  • Need to track maximum efficiently
  • Elements become irrelevant over time

Approach

  1. Use Deque: Store indices in decreasing order of values
  2. For Each Element:
    • Remove out-of-window: Pop front if deque.front() <= i - k
    • Maintain monotonic: Pop back while nums[i] >= nums[deque.back()]
    • Add current: Push i to back
    • Record max: If i >= k - 1, add nums[deque.front()] to result

Why This Works:

  • Deque front is always the maximum in current window
  • Smaller elements behind larger ones can never be max (while larger is in window)
  • Each element added and removed at most once - O(n) time

Edge Cases

  • k = 1 (each element is its own max)
  • k = n (entire array is one window)
  • Array with duplicates
  • Ascending or descending arrays

Complexity Analysis

  • Time Complexity: O(n) where n is length of nums
    • Each element pushed to deque once
    • Each element popped from deque at most once
  • Space Complexity: O(k)
    • Deque stores at most k indices

Solution

java
1class Solution {
2    public int[] maxSlidingWindow(int[] nums, int k) {
3        int n = nums.length;
4        int[] result = new int[n - k + 1];
5        Deque<Integer> deque = new LinkedList<>();  // Stores indices
6
7        for (int i = 0; i < n; i++) {
8            // Remove indices outside window
9            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
10                deque.pollFirst();
11            }
12
13            // Maintain decreasing order: remove smaller elements
14            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
15                deque.pollLast();
16            }
17
18            // Add current index
19            deque.offerLast(i);
20
21            // Record maximum for this window
22            if (i >= k - 1) {
23                result[i - k + 1] = nums[deque.peekFirst()];
24            }
25        }
26
27        return result;
28    }
29}
30
Loading visualizer...