← dsa.gleee.in
DSA · Module 03

Monotonic Stack & Deque

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!
◉ Daily Temperatures · [73, 74, 75, 71, 69, 72, 76, 73]
INITIALIZING
{ } DailyTemperatures.kt
Idiomatic Kotlin · ArrayDeque
◆ Step Explanation & Invariant
INIT

Loading...

Monotonic Invariant & Complexity