Monotonic Stack Pattern — Next Greater Element and Histogram Rectangles

Q: What is a monotonic stack?

A stack whose contents are kept in sorted order — always increasing or always decreasing from bottom to top. Before pushing a new element you pop everything that would violate that order, and each pop yields an answer: the incoming element is the popped one's nearest greater or smaller neighbour.

Q: Why is a monotonic stack O(n) if it has a nested loop?

Because each index is pushed once and popped at most once across the entire run, bounding the total stack operations at 2n. The inner while loop may run many times on one iteration and zero on the next, but summed over the whole input it does at most n pops.

Q: How does a monotonic stack solve Largest Rectangle in Histogram?

For each bar, the widest rectangle at that height runs until the first shorter bar on each side. An increasing stack gives both boundaries in one pass: the popping element is the next smaller bar on the right, and the element left underneath on the stack is the nearest smaller bar on the left. Appending a zero sentinel forces every bar to be popped and measured.

The trigger phrase is "next greater" or "previous smaller" — any question asking, for every element, about the nearest element on one side that beats it. The brute force is an O(n²) inner scan. A stack kept in sorted order does the whole thing in O(n).

The idea

Keep a stack whose values are always increasing (or always decreasing) from bottom to top. Before pushing a new element, pop everything that would break that order — and each pop is an answer, because the element causing the pop is precisely the popped element's next greater value.

def next_greater(nums):
    out = [-1] * len(nums)
    stack = []                          # holds INDICES, decreasing by value

    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            out[stack.pop()] = x        # x is the next greater for that index
        stack.append(i)

    return out                          # anything still on the stack has none

int[] nextGreater(int[] nums) {
    int[] out = new int[nums.length];
    Arrays.fill(out, -1);               // leftovers have no greater element
    Deque<Integer> stack = new ArrayDeque<>();   // INDICES, decreasing by value

    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            out[stack.pop()] = nums[i];  // nums[i] is that index's next greater
        }
        stack.push(i);
    }
    return out;
}

vector<int> nextGreater(const vector<int>& nums) {
    vector<int> out(nums.size(), -1);   // leftovers have no greater element
    vector<int> stack;                  // INDICES, decreasing by value

    for (int i = 0; i < (int)nums.size(); i++) {
        while (!stack.empty() && nums[stack.back()] < nums[i]) {
            out[stack.back()] = nums[i];
            stack.pop_back();
        }
        stack.push_back(i);
    }
    return out;
}

/* Caller owns the returned array. */
int* nextGreater(int* nums, int n) {
    int* out = malloc(n * sizeof(int));
    int* stack = malloc(n * sizeof(int));   /* INDICES */
    int top = 0;

    for (int i = 0; i < n; i++) out[i] = -1;

    for (int i = 0; i < n; i++) {
        while (top > 0 && nums[stack[top - 1]] < nums[i]) {
            out[stack[--top]] = nums[i];
        }
        stack[top++] = i;
    }
    free(stack);
    return out;
}

function nextGreater(nums) {
  const out = new Array(nums.length).fill(-1);
  const stack = [];                    // INDICES, decreasing by value

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      out[stack.pop()] = nums[i];      // nums[i] is that index's next greater
    }
    stack.push(i);
  }
  return out;
}

Store indices, not values — almost every variant needs the distance between positions, and you can always read the value back through the index.

Which direction

Four combinations, one template. Getting this table right is most of the pattern:

Want	Iterate	Pop while stack top is
Next greater	left → right	smaller than current
Next smaller	left → right	greater than current
Previous greater	right → left	smaller than current
Previous smaller	right → left	greater than current

Note the symmetry: next versus previous flips the iteration direction, greater versus smaller flips the comparison.

Daily Temperatures is next-greater with the answer expressed as a distance —

i - stack.pop() instead of the value. Next Greater Element II, on a circular array, is the same loop run over 2n iterations with i % n indexing, pushing only during the first pass.

Why it is O(n)

The nested while makes it look quadratic. It is not: each index is pushed exactly once and popped at most once, so the total number of stack operations across the whole run is at most 2n. This is the same amortisation argument as the sliding window, and it is the follow-up question.

Largest Rectangle in Histogram

The problem the pattern exists for. For each bar, the widest rectangle of that bar's height extends until the first shorter bar on each side — which is exactly previous-smaller and next-smaller. An increasing stack gives both in one pass.

For each bar, the rectangle extends until the first shorter bar on each side — which is exactly previous-smaller and next-smaller.

def largest_rectangle_area(heights):
    stack = []                            # indices, increasing height
    best = 0
    heights.append(0)                     # sentinel: forces the stack to drain

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # the new left edge is whatever is left on the stack, so the
            # width spans from just after it to just before i
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)

    heights.pop()
    return best

int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();   // indices, increasing height
    int best = 0, n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       // virtual zero sentinel
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            // the element left underneath is the nearest smaller bar
            int left = stack.isEmpty() ? -1 : stack.peek();
            best = Math.max(best, height * (i - left - 1));
        }
        stack.push(i);
    }
    return best;
}

int largestRectangleArea(const vector<int>& heights) {
    vector<int> stack;                  // indices, increasing height
    int best = 0, n = (int)heights.size();

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       // virtual zero sentinel
        while (!stack.empty() && heights[stack.back()] > h) {
            int height = heights[stack.back()];
            stack.pop_back();
            int left = stack.empty() ? -1 : stack.back();
            best = max(best, height * (i - left - 1));
        }
        stack.push_back(i);
    }
    return best;
}

int largestRectangleArea(int* heights, int n) {
    int* stack = malloc((n + 1) * sizeof(int));
    int top = 0, best = 0;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       /* virtual zero sentinel */
        while (top > 0 && heights[stack[top - 1]] > h) {
            int height = heights[stack[--top]];
            int left = (top > 0) ? stack[top - 1] : -1;
            int area = height * (i - left - 1);
            if (area > best) best = area;
        }
        stack[top++] = i;
    }
    free(stack);
    return best;
}

function largestRectangleArea(heights) {
  const stack = [];                   // indices, increasing height
  let best = 0;
  const n = heights.length;

  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i];          // virtual zero sentinel
    while (stack.length && heights[stack[stack.length - 1]] > h) {
      const height = heights[stack.pop()];
      // the element left underneath is the nearest smaller bar
      const left = stack.length ? stack[stack.length - 1] : -1;
      best = Math.max(best, height * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

Two things carry it. The zero sentinel guarantees every bar is eventually popped and measured, removing the drain-the-stack loop afterwards. And the width i - left - 1 reads the left boundary off the stack itself — the element below the popped one is, by the stack's invariant, the nearest smaller bar to the left.

Maximal Rectangle then stacks this: treat each row of a binary matrix as a histogram of

the consecutive 1s above it, and run the histogram solution per row for O(rows × cols).

Remove K Digits

The other family: building a lexicographically smallest result. Scan the digits keeping an increasing stack, popping a larger digit whenever a smaller one arrives and you still have removals left. Same mechanics, different question — greedy string construction rather than a nearest-element query.

Complexity

O(n) time, O(n) space. The stack can hold every element on strictly monotonic input, which is the worst case for space.

Mistakes that cost the round

Storing values instead of indices, then being unable to compute a width or distance.
Wrong comparison direction, which produces the mirror-image answer — usually caught

only on a test case where the array is not sorted.

Forgetting the leftovers. Elements still on the stack at the end have no next greater

element; either initialise the output to -1 or drain explicitly.

Skipping the sentinel in the histogram problem and then writing the drain loop

incorrectly.

`<` versus `<=` with duplicates. For the histogram either works, because the wider

rectangle is still found when the duplicate is popped — but be able to explain why.

What to drill

Next Greater Element I — the template.
Daily Temperatures — the same, answered as a distance.
Next Greater Element II — the circular variant.
Remove K Digits — greedy construction.
Largest Rectangle in Histogram — both boundaries at once.
Maximal Rectangle — the histogram per row.

All on the 22 DSA Patterns sheet.

Frequently asked

What is a monotonic stack?

A stack whose contents are kept in sorted order — always increasing or always decreasing from bottom to top. Before pushing a new element you pop everything that would violate that order, and each pop yields an answer: the incoming element is the popped one's nearest greater or smaller neighbour.

Why is a monotonic stack O(n) if it has a nested loop?