Interval, Boundary, And Monotonic Stack Algorithms
Asked of: Software Engineer
Last updated
![Editorial infographic with two left-to-right algorithm traces: (left) 4-step interval boundary scan showing sentinel prev and emitted missing ranges for nums=[0,1,3,7], lower=0 upper=9; (right) 4-step monotonic increasing stack trace for histogram heights [2,1,5,6,2,3] showing pushes, pops, sentinel](https://ik.imagekit.io/9osfw19dn/cheatsheets/concepts/interval-boundary-and-monotonic-stack-algorithms_FO3QFPfRo.png?tr=w-1360,q-95)
What's being tested
Tests interval boundary reasoning over sorted inputs and monotonic stack construction for nearest-smaller/greater relationships. You must show careful handling of inclusive bounds, empty gaps, merging semantics, and O(n) stack-based area computation rather than brute force.
Patterns & templates
-
Sentinel boundaries for missing ranges — scan from
lowertoupper, usingprev = lower - 1; avoid overflow withlong. -
Maximal interval detection — when
nums[i] - prev > 1, emit[prev + 1, nums[i] - 1]; skip duplicates cleanly. -
Interval merging — sort by start, then merge if
curr.start <= last.end;O(n log n)time,O(n)output space. -
Boundary convention clarity — state whether intervals are inclusive
[l, r]or half-open[l, r)before coding comparisons. -
Monotonic increasing stack for histogram area — push indices with increasing heights; pop when current height is smaller to finalize rectangles.
-
Histogram sentinel bar — append virtual height
0or loop tonso all remaining stack bars are popped and evaluated. -
Width formula after popping index
mid—width = stack.empty ? i : i - stack.top() - 1; area isheight[mid] * width.
Common pitfalls
Pitfall: Using
intforlower - 1,upper + 1, ornums[i] - prevcan overflow atInteger.MIN_VALUE/Integer.MAX_VALUE.
Pitfall: Treating adjacent intervals like
[1,2]and[3,4]as mergeable when the problem only merges overlapping intervals.
Pitfall: In histogram area, popping on the wrong comparison can mishandle equal heights; choose
>=or>deliberately and stay consistent.
Practice these
The linked practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Interval Merging And Range ManipulationCoding & Algorithms
- Intervals, Line Sweep, And Range UpdatesCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms
- Intervals, Sliding Windows, And Time-Ordered StateCoding & Algorithms
- Arrays, Sliding Windows, DP And Stack PatternsCoding & Algorithms
- Time Interval Overlap And Sweep-Line AlgorithmsCoding & Algorithms