optimization • Advanced

Monotonic Stack: Next Greater Element & Range Minimums

A Monotonic Stack maintains elements in strictly increasing or decreasing order, solving Next Greater Element, Trapping Rain Water, and Largest Rectangle in Histogram in linear O(N) time.

Intuitive Mental Model

The Shadow Cast by Skyscrapers: Taller buildings in front block your view of shorter buildings behind them. Shorter buildings are popped from the skyline stack.

C / TypeScript ImplementationHardware & Algorithmic Standard

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array(n).fill(0);
  const stack: number[] = []; // Indices of temps

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const prev = stack.pop()!;
      ans[prev] = i - prev;
    }
    stack.push(i);
  }
  return ans;
}

Key Architectural Takeaways

•Strictly O(N) Total Work: Every element is pushed and popped at most once.
•Resolves O(N^2) Brute Force: Ideal for finding nearest larger/smaller elements to left or right.

Common Coding Mistake

Storing element values instead of element indices in the monotonic stack.

Optimal Solution

Always store indices to calculate distances and positions.

Next: String Memory: UTF-8 vs UTF-16, Code Points & Graphemes