5 patterns · 27 problems
Stacks & Queues
LIFO and FIFO structures powering monotonic stacks, expression evaluation, and windowed queues.
Each pattern below starts with when to reach for it and the clue in the prompt that gives it away. Then it runs on real problems: pick one to watch the technique step by step, open its full solution, or practise it on an original problem with graded tests.
01Pattern
Design Problems
Build custom structures from stacks and queues
When to reach for it
- When you need to design and implement a custom data structure based on stacks.
Spot it in the prompt
Look for problems that require you to design a stack-based system or implement specific functionalities.
Implement Queue using Stacks
How to solve it
Animation shows the Design Problems techniqueUse two stacks: push onto an input stack, and transfer to an output stack for O(1) amortized dequeue and peek.
02Pattern
Monotonic Stack
Find nearest greater or smaller in one pass
O(n)naïve O(n^2)When to reach for it
- You encounter a problem where you need to find the nearest smaller or greater element to the left or right in an array. For example, finding the nearest greater element on the right in an array.
Spot it in the prompt
Look for problems where you need to maintain a monotonic increasing or decreasing stack to efficiently track elements' positions or values.
Daily Temperatures
How to solve it
Use a decreasing monotonic stack of indices; pop while the current temperature is warmer and record the day difference.
Nights Until a Fuller House is our own problem on the same technique: a new statement, graded in your browser.
03Pattern
Expression Evaluation
Parse and compute expressions with stacks
When to reach for it
- You encounter problems involving arithmetic or logical expression evaluation, where you need to parse and compute expressions.
Spot it in the prompt
Look for problems that involve evaluating arithmetic expressions or postfix notation.
Basic Calculator II
How to solve it
Animation shows the Expression Evaluation techniqueScan the string, applying multiplication and division immediately while pushing additive terms on a stack, then sum the stack.
Stockroom Quantity Formula is our own problem on the same technique: a new statement, graded in your browser.
04Pattern
Two Stacks
Pair two stacks to track extra state
When to reach for it
- You need to maintain a specific order or perform operations efficiently by utilizing two stacks, such as simulating a queue using two stacks.
Spot it in the prompt
Look for problems where you can simulate a specific behavior or implement operations efficiently by employing two stacks.
Evaluate Reverse Polish Notation
How to solve it
Animation shows the Two Stacks techniquePush operands on a stack; on each operator pop two operands, apply it, and push the result back.
Postfix Tape Total is our own problem on the same technique: a new statement, graded in your browser.
05Pattern
Sliding Window & Monotonic Queue
Track window extremes in amortized constant time
O(n)naïve O(n*k)When to reach for it
- You need to maintain a sliding window or find the maximum/minimum element in a window efficiently, often used in problems involving data stream processing or window-based statistics.
Spot it in the prompt
Look for problems where you need to process elements in a sliding window or maintain monotonicity in a queue, especially in array-related or streaming problems.
Sliding Window Maximum
How to solve it
Animation shows the Sliding Window & Monotonic Queue techniqueMaintain a decreasing deque of indices; pop smaller values from the back and out-of-window indices from the front so the front stays maximal.
Rolling Peak Readings is our own problem on the same technique: a new statement, graded in your browser.
After the pattern
Now solve one you haven't seen.
Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.
1,194 problems · 15,062 graded tests · free