Sliding Window Maximum

How It Works

Sliding window maximum asks for the largest value in every window of size k. Recomputing each window costs O(nk); a monotonic deque cuts this to O(n). Keep a deque of indices whose values are strictly decreasing from front to back. Before pushing a new index, pop from the back every index whose value is smaller or equal — those elements can never be a future maximum while the newer, larger element is in the window. Pop from the front when its index slides out of range. The front is always the current window's maximum.

Every index enters and leaves the deque at most once, so the whole scan is amortized O(1) per element with O(k) space.

Step-by-Step Visualization

Code

static int[] maxSlidingWindow(int[] nums, int k) {
  Deque<Integer> deque = new ArrayDeque<>();
  List<Integer> result = new ArrayList<>();
  for (int i = 0; i < nums.length; i++) {
    while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
    while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
    deque.addLast(i);
    if (i >= k - 1) result.add(nums[deque.peekFirst()]);
  }
  return result.stream().mapToInt(Integer::intValue).toArray();
}

Tips & Gotchas

Practice Problems

• 1Sliding Window Maximum
• 2Shortest Subarray with Sum at Least K
• 3Constrained Subsequence Sum
• 4Jump Game VI

About the Monotonic Deque Pattern

A deque where elements are kept in sorted order. When sliding a window across an array, the front of the deque always holds the current window's max (or min). This gives O(1) per-window extreme lookups.

Common Queue / Deque Interview Problems

• Binary Tree Level Order Traversal
• Sliding Window Maximum
• Rotting Oranges
• Shortest Path in Binary Matrix
• Implement Queue using Stacks

Frequently Asked Questions

Other Monotonic Deque Techniques