Stacks & Queues: Intermediate

Monotonic stacks, amortized queues, and the min-stack trick that unlocks O(1) everything.

Monotonic stacks, amortized queues, and the min-stack trick that unlocks O(1) everything.

Category

Python

Difficulty

intermediate

Duration

30 minutes

Challenges

0 hands-on challenges

Topics covered: Monotonic Stack Deep Dive, Queue from Two Stacks: Amortized O(1), Min-Stack and Max-Stack in O(1), BFS with Deque for Graph Problems, Stack-Based Expression Evaluation

Lesson Sections

1. Monotonic Stack Deep Dive (concepts: pyMonotonicIncreasing, pyMonotonicDecreasing, pyHistogram)

   A monotonic stack is a stack that maintains a sorted invariant. Monotonic increasing: values from bottom to top are non-decreasing. Monotonic decreasing: values from bottom to top are non-increasing. The invariant is maintained by popping elements that would violate it when a new element arrives. Those pops are where the problem's answers get recorded. This pattern appears in two critical interview problems: largest rectangle in histogram and daily temperatures. Monotonic Increasing vs Decreasin

2. Queue from Two Stacks: Amortized O(1) (concepts: pyQueueFromStacks, pyAmortized)

   This is a classic design problem with a trick that looks expensive but is not: implement a FIFO queue using only two stacks. The trick: use one stack for enqueuing ('inbox') and one for dequeuing ('outbox'). When you need to dequeue but the outbox is empty, pour the entire inbox into the outbox (reversing the order). This costs O(n) for that one operation but every element is moved at most once total, making the amortized cost O(1) per operation. Explaining Amortized O(1) Out Loud The interviewe

3. Min-Stack and Max-Stack in O(1) (concepts: pyMinStack, pyMaxStack, pyAuxStack)

   The min-stack problem: design a stack that supports push, pop, top, and get_min, all in O(1) time. The naive approach — scan the entire stack to find the minimum — is O(n) per get_min. The trick: maintain a parallel auxiliary stack that tracks the current minimum at every level. When you push a value, also push the new minimum onto the auxiliary stack. When you pop, pop from both. get_min just reads the top of the auxiliary stack. Why the Auxiliary Stack Stays Correct The key invariant: min_stac

4. BFS with Deque for Graph Problems (concepts: pyBFSLineage, pyDAGLevels, pySchemaImpact)

   BFS is the right tool when you need shortest paths in unweighted graphs or level-by-level processing. In DE interviews, the graphs are almost always dependency graphs or lineage graphs. 'Find all tables that would break if this schema change is applied' is BFS over a lineage graph. 'What is the minimum number of pipeline stages to run these tasks?' is BFS for level computation over a DAG. The algorithm is always the same. The domain framing is what makes it a DE interview problem. Shortest Path

5. Stack-Based Expression Evaluation (concepts: pyExpressionEval, pyShuntingYard, pyRPN)

   Evaluating arithmetic expressions with correct operator precedence is a classic stack problem that appears in DE interviews framed as 'parse a filter expression' or 'evaluate a query condition.' The algorithm is Dijkstra's shunting-yard algorithm. It uses two stacks: one for operands (numbers), one for operators (+, -, *, /). The key rule: when a new operator arrives, pop and evaluate all operators with higher or equal precedence before pushing the new one. Evaluate Reverse Polish Notation (Simp