Course contentsShow
← Computer Science
Lesson 401 of 2,8729. Stacks and QueuesFree lesson

Sliding Window Problems with Deques

Using deques to efficiently solve sliding window maximum and minimum problems in linear time.

Sliding Window Problems with Deques

What you'll learn: How to use deques to efficiently find the maximum or minimum value in every window of size k as it slides across an array.

The Sliding Window Challenge

Imagine watching a train pass by through a narrow window. You can only see a few cars at a time (the "window"), and as the train moves, different cars come into view while others leave. Now suppose you want to track the tallest car visible in your window at every moment—doing this naively (checking all cars in the window each time) would be slow and repetitive.

Why Deques Are Perfect

A deque (double-ended queue) solves this elegantly. Instead of storing all elements in the current window, we maintain a deque that stores only the potentially useful candidates for being the maximum (or minimum).

Here's the key insight: if a new element entering the window is larger than elements already in the deque, those smaller elements can never be the maximum while the new element is still in the window. We can safely remove them from the back of the deque.

How It Works

  1. Add elements from the back: When a new element enters the window, remove all smaller elements from the deque's back (they're now irrelevant)
  2. Remove from the front: If the front element is outside the current window, remove it
  3. Front is always the answer: The maximum for the current window is always at the deque's front

This approach processes each element exactly once (added once, removed once), achieving O(n) time complexity instead of O(n×k) for the naive approach.

Key Takeaway: Deques enable linear-time sliding window maximum/minimum problems by maintaining only relevant candidates and using both ends to add new elements and discard outdated ones.