Pattern #16

Monotonic Stack

Important interview questions, thinking patterns, increasing vs decreasing stacks, and rules for solving monotonic stack problems in Go.

Must Solve

15 core questions — solve these first.

1.Daily Temperatures
Decreasing index stack (wait for warmer day)medium
2.Next Greater Element I
Decreasing stack + Hash mapeasy
3.Next Greater Element II
Circular array processing 2x lengthmedium
4.Largest Rectangle in Histogram
Increasing stack storing heights/indexeshard
5.Online Stock Span
Monotonic stack for continuous smaller pricesmedium
6.Sum of Subarray Minimums
Previous smaller & next smaller boundsmedium
7.Remove K Digits
Monotonic increasing stack for smallest numbermedium
8.Trapping Rain Water
Monotonic decreasing stack bounded areahard
9.Asteroid Collision
Stack collision resolutionmedium
10.Maximum Width Ramp
Monotonic decreasing index stackmedium
11.Next Greater Node In Linked List
Convert list to array + monotonic stackmedium
12.132 Pattern
Search 3rd element backwards with monotonic stackmedium
13.Remove Duplicate Letters
Monotonic stack + char count & visited setmedium
14.Sum of Subarray Ranges
Sum of maxes minus sum of minsmedium
15.Final Prices With a Special Discount in a Shop
Monotonic stack next smaller or equaleasy

Also Important

7 more questions worth practicing.

16.Buildings With an Ocean View
Monotonic decreasing height stack from rightmedium
17.Number of Visible People in a Queue
Monotonic decreasing stack pop counthard
18.Car Fleet
Sort by position + monotonic arrival time stackmedium
19.Shortest Unsorted Continuous Subarray
Monotonic stack find out-of-order boundsmedium
20.Maximum Subarray Min-Product
Monotonic stack min element + Prefix Summedium
21.Steps to Make Array Non-decreasing
Monotonic stack step simulationmedium
22.Total Steps to Make Array Non-decreasing
Monotonic stack step eliminationmedium

How to Think

Need next greater?Monotonic Stack (Decreasing)
Need next smaller?Monotonic Stack (Increasing)
Need previous greater / smaller?Monotonic Stack
Need nearest bigger / smaller element?Monotonic Stack
Need distance to next bigger value?Store indexes (not only values)
Need rectangle width?Previous Smaller + Next Smaller

Go Monotonic Stack Template

Next Greater Element Template (Decreasing Stack)

stack := []int{} // Stores indexes
result := make([]int, len(nums))

for i := 0; i < len(nums); i++ {
    // Current element solves any smaller elements waiting on stack
    for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
        idx := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result[idx] = nums[i] // Found Next Greater!
    }
    stack = append(stack, i) // Push current index
}

👉 Total Time: O(n) | Space: O(n) (Each element is pushed once & popped once)

Increasing vs Decreasing Monotonic Stack

Decreasing Stack [8, 6, 4, 2]

Use for: Next Greater Element
Why: Smaller elements wait for a bigger element to resolve them

Increasing Stack [1, 3, 5, 7]

Use for: Next Smaller Element
Why: Bigger elements wait for a smaller element to resolve them

Visual Memory Rule

Waiting values on stack:  [75, 71, 69]
Current element arrives:  72
Pop 69 & 71 → Push 72!
New stack state:          [75, 72]

💡 Golden Rule: "Keep only the unresolved values in sorted stack order, and let each new value resolve whatever it can."

Common Interview Mistakes

1. Wrong Stack Order Direction

Using an increasing stack when you need Next Greater (which requires a decreasing stack of waiting values).

2. Popping Only Once with IF

One new large element can resolve multiple smaller unresolved elements. Always use a while loop!

3. Storing Values Instead of Indexes

Storing values prevents calculating distance or width (i - stack.Top). Store indexes!

4. Assuming Nested Loop is O(n²)

Each element is pushed once and popped at most once, making the total work strictly O(n).

Interview Rules

1. Next greater? → Decreasing Monotonic Stack
2. Next smaller? → Increasing Monotonic Stack
3. Previous greater/smaller? → Monotonic Stack
4. Distance needed? → Store indexes on stack
5. Width needed? → Store indexes on stack
6. One current solves many previous? → Keep popping with while loop
7. Circular Array? → Process array twice (i % n)
8. Overall Complexity → O(n) time, O(n) space

Small Rules

Rule 1:Each element is pushed once & popped once, total time is O(n).
Rule 2: A nested `while` inside a loop does NOT mean O(n²) because items leave the stack only once.
Rule 3: Store indexes when distance, width, or position is needed.
Rule 4: Store values when only direct element comparison is needed.
Rule 5: Circular array next greater element uses `i % n` over 2*n iterations.

Production Thinking

Stock Price Monitoring → For every stock price, find when next higher price occurs in O(n)

Server Load Spikes → Identify next time CPU load exceeds current threshold

Event Latency Thresholds → Process request latency spikes without O(n²) forward scanning

E-Commerce Price Discounts → Next Smaller element for special discount applying

Remember This

Next Greater            → decreasing stack
Next Smaller            → increasing stack
Need distance           → store indexes
Current solves top?     → pop
Still solves top?       → keep popping
Then                    → push current
Each element            → push once, pop once (O(n))

💡 Golden Rule: "Keep only the unresolved values in sorted stack order, and let each new value resolve whatever it can."