Skip to main content
Sliding Window

Monotonic Window

Use a deque (double-ended queue) inside the window to maintain elements in sorted order. This lets you find the min or max of any window in O(1). Used in sliding window maximum/minimum.

O(n)
·
O(n)

How It Works

A monotonic window pairs the sliding window with a deque that keeps candidate elements in decreasing (for max) or increasing (for min) order. When a new element arrives, pop everything smaller than it off the back — those elements can never be a future maximum because the newcomer is both larger and newer. Push the new index, and evict the front when it falls outside the window.

The front of the deque therefore always holds the current window's extreme in O(1). Since every index is pushed once and popped at most once, the entire scan runs in O(n), a dramatic improvement over the O(n·k) cost of rescanning each window for its max.

Step-by-Step Visualization

Window size K=3. Build first window
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
Window [0..2]
Deque[3, -1]
Max3
1/5

Code

Java
static int[] maxSlidingWindow(int[] nums, int k) {
  Deque<Integer> deque = new ArrayDeque<>(); // stores indices
  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();
}

// Example: maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3)

Tips & Gotchas

1Use a deque to maintain monotonic order within the window
2Remove elements from back that are smaller (for max) or larger (for min)
3Remove elements from front that fall outside the window

Practice Problems

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

About the Sliding Window Pattern

Instead of recalculating from scratch for every subarray, keep a 'window' that slides across the array. As the window moves right, add the new element and remove the old one. This turns O(n·k) brute force into O(n).

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

Why can't I just track a single max variable as the window slides?

A single variable fails when the maximum itself slides out of the window, because you have no record of the second-best element to fall back on. The monotonic deque preserves exactly the chain of fallback candidates, each one a potential future maximum.

Should the deque store values or indices?

Store indices. You need the index to know when the front element has left the window, and you can always recover the value from the array. Storing values alone makes window-expiry checks impossible when duplicates exist.

Why is a heap worse than a deque here?

A heap gives O(log n) insertions and requires lazy deletion for expired elements, yielding O(n log n) overall. The monotonic deque exploits the ordered arrival of elements to achieve amortized O(1) per step, or O(n) total.