Google Interview Cheat Sheet — Monotonic Stack & Deque
Amortized O(N) · Total Ops ≤ 2N
1. Pattern Recognition Triggers
- Next Greater / Smaller Element: "How many days until a warmer temp?", "Stock Span", "Next Greater".
- Largest Area / Boundary Span: "Largest Rectangle in Histogram", "Maximal Rectangle", "Sum of Subarray Minimums".
- Sliding Window Max/Min in O(N): Fixed-size window asking for extrema without an O(N log K) heap.
2. Monotonic Invariant
- Elements inside the stack/deque stay strictly increasing (find Next Smaller) or strictly decreasing (find Next Greater / Window Max).
- Whenever an incoming element violates the order, popping resolves the waiting element's boundary in O(1)!
- Always store indices (not just values) so you can compute widths
(i - j) and expire old window items.
3. Amortized O(N) Proof
- Interviewers frequently ask: "Isn't a while loop inside a for loop O(N²)?"
- Proof: Every index
0..N-1 is pushed ONCE and popped AT MOST ONCE.
- Therefore, across the entire algorithm, total push + pop operations ≤ 2N → strict O(N) time!
Loading...
Monotonic Invariant & Complexity