Monotonic Stack

Maintaining sorted stacks for next greater/smaller elements.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Monotonic Stack Concept

A monotonic stack keeps elements in sorted order (strictly increasing or decreasing). When processing a new element, pop elements that violate the order. Each element pushed/popped once → O(n) total.

Type	Order	Use Case
Monotonic Increasing	Bottom to top: small → large	Next smaller, previous smaller
Monotonic Decreasing	Bottom to top: large → small	Next greater, previous greater

Next Greater Element

For each element, find the first greater element to its right. Use decreasing stack: pop smaller elements, current is their next greater.

Gonext-greater-element.go

20 linesLn 1, Col 1Go

Stack maintains decreasing sequence. When nums[i] > stack top, it's the next greater for that index. Pop and record. Push current index. Remaining in stack have no next greater (-1).

Next Smaller Element

Gonext-smaller-element-(increasing-stack).go

18 linesLn 1, Col 1Go

Increasing stack: pop when current < stack top. Current is next smaller for popped indices.

Largest Rectangle in Histogram

Find largest rectangular area in histogram. For each bar, find left/right boundaries where height >= current. Monotonic increasing stack finds previous/next smaller in O(n).

Golargest-rectangle-in-histogram.go

36 linesLn 1, Col 1Go

For each bar, find first smaller on left and right. Width = right - left - 1. Area = height * width. Stack finds boundaries in O(n).

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.