Stack + Binary Search Drills

Mixed practice problems that combine monotonic stack reasoning with binary search optimization — two patterns that complement each other.

12 min readLeetCode Patterns for InterviewsCode

The Pattern

Monotonic stacks excel at finding the next greater or smaller element in O(n). Binary search on answer finds optimal numeric bounds in O(log range × n). They seem unrelated — yet they pair naturally when a problem requires both position tracking (stack) and value optimization (binary search).

Common combinations include: using a stack to compute ranges or histograms (next smaller element), then using binary search over those ranges; or using a stack to maintain candidates and binary search to query them (e.g., the 132 pattern where a stack tracks potential '3' values while binary search checks for a '2' between '1' and '3').

Monotonic decreasing stack — tracking next greater elements

Temperatures stack (value→next greater)

72→—top

69→72

71→72

75→76

74→76

73→76

Stack gives you position; binary search gives you a bound

When a problem involves 'find the minimum of maximums' over subarrays defined by next-smaller-element boundaries, the stack computes the boundaries and binary search on answer tests the feasibility. The same pattern appears in histograms, rain water, and subarray minimums.

Gomonotonic-stack-—-next-greater-element-template.go

21 linesLn 1, Col 1Go

The stack stores indices with decreasing values. When we see a larger value nums[i], it becomes the next greater for all smaller values on the stack. The stack is monotonic decreasing (values at indices are strictly decreasing).

Template

When combining stack and binary search, follow this general approach:

Identify the decision variable: what numeric bound are we binary searching over? (e.g., capacity, speed, largest sum)
Compute structural info with a stack: precompute next-smaller or next-greater element indices in O(n).
Use the structural info in feasibility: the precomputed ranges let you evaluate a candidate answer faster, or let you reason about subarray properties.
Binary search over the answer: use the standard search-on-answer template with feasibility derived from the stack's output.

Problems

#739Daily TemperaturesMediumMonotonic stack — next greater element · O(n) time · O(n) space #901Online Stock SpanMediumMonotonic stack — cumulative span · O(1) amortized per call time · O(n) space #456132 PatternMediumMonotonic stack + binary search · O(n) time · O(n) space #155Min StackMediumStack design — auxiliary stack · O(1) per operation time · O(n) space

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

Stage 1 · Code

Stack & Binary Search