Sign in to watch this lesson
Algorithms - Arrays · 4:45
Minimum Stack, Minimum Queue and Sliding-Window Minimum
A stack keeps its minimum in O(1) by caching the minimum below every element, but a queue removes from the other end. We slide a window of 3 over [1, 3, -1, -3, 5, 3, 6, 7] with a monotone deque whose values climb like a staircase: newer, smaller values bulldoze older ones off the back and expired indices fall off the front, so every window minimum is read from the front in amortized O(1). Then we build a queue from two min-stacks, which works for any associative operation such as gcd or OR, and measure the rescan against the deque on a million values.
You will learn
- Implement a min-stack that stores (value, minimum below) so push, pop and min are all O(1)
- Compute every sliding-window minimum or maximum in O(n) with a monotone deque of indices, and explain the amortized bound
- Choose the strict comparison (or store indices) so repeated values are handled correctly
- Build a queue from two stacks that supports any associative operation (min, gcd, OR) when no inverse exists