Monotonic Stacks: Next Greater Element, Histogram & Subarray Mins

Dominance Pruning & Two-Sided Boundary Discovery

Suppose we want to find, for every bar $H[m]$ in a histogram $H[0 \dots N-1]$, the largest rectangle of height $H[m]$ that can be formed using $m$ as the shortest (limiting) bar. That rectangle extends left to the nearest index $L < m$ with $H[L] < H[m]$, and extends right to the nearest index $R > m$ with $H[R] < H[m]$, giving width $(R - L - 1)$ and area $H[m] \cdot (R - L - 1)$.

How does a Monotonic Increasing Stack find both $L$ and $R$ for every $m \in [0, N-1]$ in a single left-to-right scan? Maintain a stack of indices $i_0 < i_1 < \dots < i_k$ such that $H[i_0] \le H[i_1] \le \dots \le H[i_k]$. When scanning index $R$:

• While the stack is non-empty and $H[\text{stack.top()}] > H[R]$, let $m = \text{stack.pop()}$.
• Right Boundary ($R$): Because $m$ survived on the stack until $R$ arrived, no index in $(m, R)$ had height $< H[m]$; thus $R$ is the exact Next Smaller Element to the right of $m$!
• Left Boundary ($L$): What is the new stack.top() sitting immediately below $m$? Every element originally between $L = \text{stack.top()}$ and $m$ was already popped before $m$ was pushed, meaning all of them were $\ge H[m]$ while $H[L] \le H[m]$. Thus $L$ is the exact Previous Smaller Element to the left of $m$!

By the aggregate amortized method, each of the $N$ indices is pushed onto the stack exactly once and popped at most once, bounding total stack operations to $\le 2N = O(N)$ time.

Monotonic Stack Variants & Boundary Semantics

Visualizing Histogram Rectangle Expansion $[L+1 \dots R-1]$ Upon Pop

Single-Pass Sentinel-Flushed Histogram Algorithm

Production Implementation: Largest Histogram Rectangle & Subarray Minimums Sum

#include <algorithm>
#include <cstdint>
#include <vector>

// O(N) Single-Pass Largest Rectangle in Histogram with virtual R = N sentinel (height 0)
std::int64_t largest_rectangle_area(const std::vector<int>& heights) {
  const std::size_t n = heights.size();
  std::vector<std::size_t> st;
  st.reserve(n + 1);
  std::int64_t max_area = 0;

  for (std::size_t r = 0; r <= n; ++r) {
    const int cur_h = (r == n) ? 0 : heights[r];
    while (!st.empty() && heights[st.back()] >= cur_h) {
      const std::int64_t h = heights[st.back()];
      st.pop_back();
      const std::size_t width = st.empty() ? r : (r - st.back() - 1);
      max_area = std::max(max_area, h * static_cast<std::int64_t>(width));
    }
    st.push_back(r);
  }
  return max_area;
}

// O(N) Single-Pass Sum of Subarray Minimums using Asymmetric Tie-Breaking
// Pop condition arr[st.back()] >= cur means:
//   - Right boundary r is the first element <= arr[m]
//   - Left boundary l (new st.back()) is strictly < arr[m]
std::int64_t sum_of_subarray_minimums(const std::vector<int>& arr) {
  const std::size_t n = arr.size();
  std::vector<std::size_t> st;
  st.reserve(n + 1);
  std::int64_t total_sum = 0;

  for (std::size_t r = 0; r <= n; ++r) {
    const int cur = (r == n) ? -2147483648 : arr[r];
    while (!st.empty() && (r == n || arr[st.back()] >= cur)) {
      const std::size_t m = st.back();
      st.pop_back();
      const std::size_t left_count = st.empty() ? (m + 1) : (m - st.back());
      const std::size_t right_count = r - m;
      const std::int64_t ways = static_cast<std::int64_t>(left_count) * static_cast<std::int64_t>(right_count);
      total_sum += static_cast<std::int64_t>(arr[m]) * ways;
    }
    st.push_back(r);
  }
  return total_sum;
}