Stacks & Queues

One-line trigger: "Process in LIFO order (stack), FIFO order (queue), or maintain a running answer over a sliding window (deque)."

The most recently opened bracket must be the first one closed — that is LIFO, so a stack does the matching for free.

Reversing a stack into a second stack turns LIFO into FIFO. Only refill when the output stack is empty — that is what makes it amortised O(1) instead of O(n).

An element that is smaller than a later element can never be the window max again — evict it immediately. What survives is a decreasing deque of indices…

Everything rots simultaneously, so seed the queue with all rotten cells before the loop starts. BFS levels then equal elapsed minutes.

Wrap indices with % capacity to reuse freed slots. Track an explicit count so "full" and "empty" are never ambiguous.