Stack / Monotonic Stack

One-liner: keep a stack of items that are still waiting for an answer, and settle them the moment something that answers them arrives.

The analogy

Picture people standing in a line to look at a skyline, each person waiting to find the first taller building to their right. When a new, taller building appears, every shorter one waiting at the back of the line gets their answer at once and walks away. Only the ones still taller than the newcomer keep waiting. A stack is that line, and the top is always the most recent waiter. Each item is pushed once and popped once, so the whole scan is O(n).

Recognition signals

Reach for a stack when you see:

1. Matching or nesting: brackets, tags, nested structure — the most recent opener must close first (last in, first out).
2. "Next greater", "next smaller", "previous greater" element for every position.
3. "How many days / steps until something bigger or smaller happens?"
4. A rectangle, span or area where each element is the limiting value over a range (the smallest bar decides the height).
5. A nested-loop answer where the inner loop scans right until it finds a bigger value.

Step-by-step walkthrough

Take Daily Temperatures on [73, 74, 75, 71, 69, 72, 76, 73]. The stack holds indices of days still waiting for a warmer one.

1. Day 0 (73): stack empty, push 0.
2. Day 1 (74): 73 is colder, pop day 0 and answer 1 - 0 = 1. Push 1.
3. Day 2 (75): pop day 1, answer 1. Push 2.
4. Days 3 and 4 (71, 69): each is colder than the top, so just push. Stack is [2, 3, 4].
5. Day 5 (72): pop day 4 (answer 1) and day 3 (answer 2). Day 2 (75) is warmer, stop. Push 5.
6. Day 6 (76): pops days 5 and 2. Push 6. Day 7 (73) pushes. Leftovers get 0.

Store indices, not values: you can always look up the value, and you need the index to compute distances.

Code template

// NextGreater returns, for each i, the index of the next element strictly greater than
// nums[i], or -1 if none. The stack holds indices still waiting for an answer;
// their values are non-increasing from bottom to top.
func NextGreater(nums []int) []int {
	res := make([]int, len(nums))
	for i := range res {
		res[i] = -1
	}
	stack := []int{} // indices of unresolved items
	for i, v := range nums {
		for len(stack) > 0 && nums[stack[len(stack)-1]] < v {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[top] = i // v is the answer for top
		}
		stack = append(stack, i)
	}
	return res
}

Why each part exists:

Solutions

Valid parentheses (plain stack)

No ordering rule here — just push openers and make sure each closer matches the top. A non-empty stack at the end means something was never closed.

// IsValid: are all brackets closed by the right type, in the right order?
func IsValid(s string) bool {
	pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		c := s[i]
		if open, isClose := pairs[c]; isClose {
			if len(stack) == 0 || stack[len(stack)-1] != open {
				return false
			}
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, c)
		}
	}
	return len(stack) == 0 // leftovers are unclosed brackets
}

Daily temperatures

The template, but the answer is a distance (i - j) instead of a value.

// DailyTemperatures: days to wait until a warmer day (0 if never).
func DailyTemperatures(temps []int) []int {
	res := make([]int, len(temps))
	stack := []int{}
	for i, t := range temps {
		for len(stack) > 0 && temps[stack[len(stack)-1]] < t {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[j] = i - j
		}
		stack = append(stack, i)
	}
	return res
}

Next greater element, circular

Walk the array twice (indices 0..2n-1, using i % n) so elements near the end can see the beginning. Push only during the first pass.

// NextGreaterElements: next greater in a circular array (-1 if none).
// Walk the array twice; only push during the first pass.
func NextGreaterElements(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	for i := range res {
		res[i] = -1
	}
	stack := []int{}
	for i := 0; i < 2*n; i++ {
		v := nums[i%n]
		for len(stack) > 0 && nums[stack[len(stack)-1]] < v {
			res[stack[len(stack)-1]] = v
			stack = stack[:len(stack)-1]
		}
		if i < n {
			stack = append(stack, i)
		}
	}
	return res
}

Largest rectangle in a histogram

Here the pop produces an area. When a shorter bar arrives, each taller bar on the stack can no longer extend right. Its width runs from the new stack top (the nearest shorter bar on the left) to the current index. A sentinel bar of height 0 at the end flushes everything.

// LargestRectangleArea: largest rectangle inside a histogram.
// Stack of increasing heights. A shorter bar pops taller ones; each popped bar's
// rectangle extends left to the new stack top and right to the current index.
func LargestRectangleArea(heights []int) int {
	best := 0
	stack := []int{} // indices with increasing heights
	for i := 0; i <= len(heights); i++ {
		h := 0 // sentinel bar of height 0 flushes the stack at the end
		if i < len(heights) {
			h = heights[i]
		}
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= h {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			left := -1
			if len(stack) > 0 {
				left = stack[len(stack)-1]
			}
			best = max(best, height*(i-left-1))
		}
		stack = append(stack, i)
	}
	return best
}

Complexity

Every index is pushed once and popped at most once, so the inner for is amortized O(1) per element, not O(n).

Common mistakes

Practice ladder

Ordered Easy → Hard. Titles rarely say "stack" — look for matching, or for a "first thing that beats me" question.

1. 1.
   Valid Parentheses

   The most recent opener must be the first to close.
   Easy
2. 2.
   Next Greater Element I

   Solve it for the whole array first, then look up the queries.
   Easy
3. 3.
   Daily Temperatures

   The answer is a distance, so remember positions.
   Medium
4. 4.
   Next Greater Element II

   The array wraps around.
   Medium
5. 5.
   Evaluate Reverse Polish Notation
   Medium
6. 6.
   Remove K Digits

   Drop a digit whenever the next one is smaller.
   Medium
7. 7.
   Largest Rectangle in Histogram

   For each bar, how far can it extend left and right before a shorter bar?
   Hard
8. 8.
   Trapping Rain Water

   Water is held between a wall and the next taller wall.
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.