Cheat Sheet
Quick-reference for the entire course. Bookmark this page.
Problem → Data Structure
| Problem Goal | Data Structure | Chapter |
|---|---|---|
| Next / Previous Greater or Smaller Element | Monotonic Stack (decreasing or increasing) | 1 |
| Range where element is min/max (boundaries) | Two monotonic stacks (PSE + NSE or PGE + NGE) | 1, 3 |
| Subarrays with bitwise OR / GCD property | Monotonic Stack with custom eclipse condition | 1 |
| Sliding window min/max (fixed K) | Monotonic Deque | 2 |
| Longest subarray with max - min ≤ X | Dual Deques + Two Pointers | 2 |
| DP: min/max over sliding range of states | Monotonic Deque | 2 |
| Largest rectangle in histogram | Monotonic Stack (boundaries → area) | 3 |
| Maximal rectangle in binary matrix | Row-by-row height accumulation + histogram | 3 |
| Sum of subarray minimums / maximums | Contribution technique (boundaries → count × value) | 3 |
| Histogram with variable-width bars | Weighted stack (width accumulation on pop) | 3 |
| Smallest number after removing K digits | Greedy increasing stack with pop budget | 4 |
| Lexicographically smallest subsequence of length L | Greedy stack with budget = N - L | 4 |
| Remove duplicate letters (smallest result) | Greedy stack with dynamic pop condition (check remaining count) | 4 |
| Build a Cartesian Tree in O(N) | Monotonic Stack (right spine invariant) | 5 |
| Range minimum query via tree structure | Cartesian Tree (LCA = RMQ) | 5 |
| Count arrays with same Cartesian Tree structure | Tree DP on Cartesian Tree | 5 |
| DP: min(dp[j] + A[j] * B[i]) — non-separable cost | Convex Hull Trick (deque of lines) | 6 |
| Lower envelope with unsorted slopes | Li Chao Tree | 6 |
| Rolling min/max on infinite stream | Monotonic Deque (streaming mode) | 7 |
| Maximal rectangle in dynamic grid | Height arrays + histogram re-solve on update | 7 |
| Range queries on stack properties ([L, R]) | Offline sweep + Stack + Fenwick Tree | 8 |
| Max/min in every K×K subgrid | 2D Monotonic Queue (horizontal + vertical pass) | 8 |
Chain Type → Stack Type
| Chain Type | Stack Ordering | Use When |
|---|---|---|
| Decreasing | Bottom = largest, top = smallest | Finding next/previous greater element |
| Increasing | Bottom = smallest, top = largest | Finding next/previous smaller element |
| OR-chain | Pop when new bits turn on | Subarray OR properties |
| GCD-chain | Pop when GCD shrinks | Subarray GCD properties |
The Two Pop Conditions (Deque)
| Pop Type | Direction | Trigger | Meaning |
|---|---|---|---|
| Eclipse | Back (right end) | New element dominates old | Value obsolescence — the old element can never be the answer |
| Expiration | Front (left end) | Index outside window | Time obsolescence — the old element is too far away |
Complexity Reference
| Technique | Time | Space |
|---|---|---|
| Monotonic Stack (any variant) | O(N) amortized | O(N) |
| Monotonic Deque (sliding window) | O(N) amortized | O(K) |
| Largest Rectangle in Histogram | O(N) | O(N) |
| Maximal Rectangle in Matrix | O(N × M) | O(M) |
| Cartesian Tree Construction | O(N) | O(N) |
| Convex Hull Trick (sorted slopes + queries) | O(N) | O(N) |
| Convex Hull Trick (sorted slopes, unsorted queries) | O(N log N) | O(N) |
| Li Chao Tree | O(N log MAX_X) | O(N log MAX_X) |
| 2D Monotonic Queue (K×K subgrid) | O(N × M) | O(N × M) |
| Offline Range Queries (sweep + BIT) | O((N + Q) log N) | O(N + Q) |
The Core Principle
One sentence to remember everything:
Discard what can never matter again. The data structure that does this is the monotonic stack.
Eclipse = the new element makes the old one permanently irrelevant. Whether the "elements" are integers, histogram bars, linear functions, or bit patterns — the pattern is identical. Scan, pop the eclipsed, push the new arrival. O(N).