Monotonic Deque

Sliding Window Minimum

Same technique but with an increasing deque. Remove all larger elements from the back when adding a new element. The front is always the window's minimum.

O(n)

O(k)

How It Works

Sliding window minimum is the mirror of the maximum problem: flip every comparison. Maintain a deque of indices whose values increase from front to back. When a new element arrives, pop from the back all indices holding larger-or-equal values — a smaller newcomer makes them permanently irrelevant — then push the new index. Evict the front index once it falls outside the window. The front always names the window's minimum.

Each element is pushed once and popped at most once, so all n windows are answered in O(n) total time and O(k) space. Keeping both an increasing and a decreasing deque side by side yields simultaneous min and max, the core of bounded-range subarray problems.

Step-by-Step Visualization

Min in each window of size k=3

Window [0..2]

Deque (increasing)[3, 4]

Min3

1/3

Code

Java

static int[] minSlidingWindow(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

1Same as qd-max but maintain an increasing deque

2Remove from back if current element is smaller

3Front of deque is always the minimum in the window

Practice Problems

1Sliding Window Median
2Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
3Shortest Subarray with Sum at Least K
4Min Stack

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.

Key insight

BFS = queue. If you need shortest path in an unweighted graph or level-order traversal, reach for a queue. Monotonic deques solve sliding window extremes in O(n).

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

What actually changes between the max and min versions?

Only the back-pop comparison: the max version removes smaller values to keep the deque decreasing, while the min version removes larger values to keep it increasing. Window eviction at the front and the overall amortized O(n) analysis are identical.

When would I run both deques at once?

Problems constraining the spread of a window — such as longest subarray where max minus min stays within a limit — need the current extremes simultaneously. Maintain a decreasing deque for the max and an increasing one for the min, shrinking the window from the left whenever the gap exceeds the bound.