Interval, Boundary, And Monotonic Stack Algorithms

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 lower to upper, using prev = lower - 1; avoid overflow with long.

• 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 0 or loop to n so all remaining stack bars are popped and evaluated.

• Width formula after popping index mid — width = stack.empty ? i : i - stack.top() - 1; area is height[mid] * width.

Common pitfalls

Pitfall: Using int for lower - 1, upper + 1, or nums[i] - prev can overflow at Integer.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.