Monotonic Stack — Previous Greater Element

What does it solve?

For every element, find the previous greater element: the nearest value to its left that is strictly greater (or none). Brute force scans left from each index for O(N²). A monotonic decreasing stack does it in one left-to-right pass.

Key insight (the twist vs. next-greater): the answer is read off the stack, not recorded on a pop. When you reach i, pop everything ≤ a[i] (those are dominated and can never be a future element's previous greater). Whatever remains on top is a[i]'s previous greater. If the stack is empty, there is none. Then push i, keeping it decreasing.

The core idea

// decreasing stack, answer = top on arrival
res[] = -1, stack = empty
for i in 0..n-1:
  while stack && a[top] <= a[i]: pop
  if stack: res[i] = a[top]
  push i

Complexity

Time complexity

O(N)

Each index is pushed once and popped at most once. The inner while loop's total work across the whole scan is bounded by N, so it stays linear.

Space complexity

O(N)

The stack holds at most N indices (a strictly decreasing sequence), plus the result array. No nested rescans.

Examples & edge cases

Live animation — decreasing stack, top is the previous greater on arrival

processed (answer set) in stack (candidate) not scanned yet

i (scanning) stack top popping (≤ a[i]) answer read

Input array

Monotonic stack (bottom → top, values decreasing)

Previous greater element (-1 = none)

Current step detail

i = — stack = — pops = — processed = —

Step — of —

—

scan pointer

stack top

—

= prev greater

pops

—

total so far

processed

—

answers set

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	a[i]	Stack (vals)	Rule	Action	Result

C++ implementation

previous_greater_element.cpp

#include <bits/stdc++.h>
using namespace std;

// Previous Greater Element (nearest greater to the LEFT).
// Decreasing stack of indices; on arrival the top IS the answer.
vector<int> prevGreater(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);   // -1 = no greater element to the left
    stack<int> st;            // stores indices, values decreasing

    for (int i = 0; i < n; i++) {
        // drop everything <= a[i]: they can't be anyone's previous greater
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();
        if (!st.empty()) res[i] = a[st.top()];   // top is the previous greater
        st.push(i);              // keep the stack decreasing
    }
    return res;
}

int main() {
    vector<int> a = {2,1,2,4,3};
    vector<int> r = prevGreater(a);
    for (int x : r) cout << x << " "; // -1 2 -1 -1 4
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars