Monotonic Stack: Next Element and Subarray Contribution

Learning Outcome

Find nearest greater/smaller boundaries and contribution counts in linear time.

Pattern Recognition

Item	Detail
Core signal	The problem asks for next greater/smaller, visibility, histogram area, or sum over subarray minimum/maximum.
Use when	A value stays useful until a future value proves it is no longer the nearest boundary.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

The stack is a compressed set of candidates whose nearest resolving value has not appeared yet.

Exact Practice Question Names

Next Greater Element
Daily Temperatures
Largest Rectangle in Histogram
Sum of Subarray Minimums
Sum of Subarray Ranges
Number of Visible People in a Queue

Interview Approach

Decide increasing or decreasing stack.
Store indices, not only values.
Pop while the current value resolves the stack top.
For contribution problems, define strict vs non-strict tie handling.

Pseudocode

stack = []
for i from 0 to n:
  while stack not empty and current resolves stack.top:
    mid = stack.pop()
    left = stack.top or boundary
    use left and i as boundaries for mid
  stack.push(i)

Sample Dry Run

For histogram [2,1,5,6,2,3], value 2 at index 4 resolves bars 6 and 5, calculating rectangles before those bars lose their right boundary.

Edge Cases

Duplicate values
Sentinel cleanup at end
Strict vs non-strict comparisons
Modulo for large contribution sums

Common Mistakes

Using values instead of indices
Wrong tie direction causing double count
Forgetting the final sentinel pass

Complexity

Item	Detail
Expected time	O(n).
Expected space	O(n).

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.