Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Monotonic Stack
DSA

Monotonic Stack

Understand how monotonic stacks efficiently solve next greater, next smaller, and range-based problems.

A monotonic stack keeps elements in increasing or decreasing order.

When a new element breaks the order, pop until the order is restored.

Its core advantage:

Each element is pushed and popped at most once → O(n) instead of O(n²).

Focus on recognizing:

“Next/previous” + “greater/smaller” = Monotonic Stack

Pattern Table

PatternTypical QuestionsTrigger
Next GreaterNext Greater Element, Daily TempsPop smaller, assign on pop
Stock SpanSpan of today’s priceKeep useful previous indices
Largest RectangleLargest Rectangle in HistogramPop taller bars, compute width

Mental Trigger

Pop while order is violated → Process popped → Push current.

1. Generic Monotonic Stack Template (Base)

Watch the decreasing stack resolve [4, 5, 2, 25] — index 1 (value 25) pops two waiting indices at once. Press ▶ to animate, or step through manually with the arrows and speed control.

Next Greater Element (Monotonic Decreasing Stack)

For each element, find the first element to its right that is larger. A decreasing stack of indices holds elements still awaiting their answer; when a bigger element arrives it resolves (pops) every smaller one.

Array [4,5,2,25]. The stack (drawn with VALUES) holds indices whose next-greater is still unknown, kept in strictly DECREASING value order. When nums[i] is bigger than the top, that top gets nums[i] as its answer and is popped. Leftovers end with -1. The state chips show the running result; each index is pushed and popped once → O(n).

STACK VISUALIZER
Steps –
TOP ↓
4
STACK (LIFO)
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        result = [-1, -1, ..., -1]
                      
                        2
                        for i from 0 to n-1:
                      
                        3
                          while stack not empty AND nums[stack.top] < nums[i]:
                      
                        4
                            j = pop stack;  result[j] = nums[i]
                      
                        5
                          push i onto stack
                      
                        6
                        return result
                      
public void monotonicStack(int[] nums) {
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < nums.length; i++) {

        while (!stack.isEmpty() && /* order violated */) {
            int j = stack.pop();
            // process j — nums[i] answers j
        }

        stack.push(i);
    }
}
def monotonic_stack(nums: list[int]) -> None:
    stack = []

    for i, num in enumerate(nums):

        while stack and /* order violated */:
            j = stack.pop()
            # process j — num answers j

        stack.append(i)
void monotonicStack(vector<int>& nums) {
    stack<int> st;

    for (int i = 0; i < nums.size(); i++) {

        while (!st.empty() && /* order violated */) {
            int j = st.top(); st.pop();
            // process j — nums[i] answers j
        }

        st.push(i);
    }
}
function monotonicStack(nums) {
  const stack = [];

  for (let i = 0; i < nums.length; i++) {

    while (stack.length && /* order violated */) {
      const j = stack.pop();
      // process j — nums[i] answers j
    }

    stack.push(i);
  }
}

Everything else in Monotonic Stack is just a modification of this template.

Two rules to fill the placeholder:

  • Decreasing stack (pop smaller) → finds next greater
  • Increasing stack (pop larger) → finds next smaller

Pattern 1: Next Greater Element

A decreasing stack of values; each arrival resolves everyone smaller.

Next Greater Element

For each element, find the next greater element to its right. A decreasing stack holds elements waiting for their answer. When a bigger element arrives, it resolves all smaller ones.

Array: [4,5,2,25]. Decreasing stack of values. Each new element pops everything smaller — those popped elements get the new element as their answer.

ARRAY VISUALIZER
Steps –
4
0
5
1
2
2
25
3
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        stack = []                  // values waiting for their NGE
                      
                        2
                        for x in nums:
                      
                        3
                          while stack and x > stack.top:
                      
                        4
                            answer[pop()] = x
                      
                        5
                          push(x)
                      
                        6
                        leftovers → answer = -1

Code

public int[] nextGreaterElement(int[] nums) {
    int[] result = new int[nums.length];
    Arrays.fill(result, -1);

    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }

        stack.push(i);
    }

    return result;
}
def next_greater_element(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)

    return result
vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> result(nums.size(), -1);
    stack<int> st;

    for (int i = 0; i < nums.size(); i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            result[st.top()] = nums[i];
            st.pop();
        }

        st.push(i);
    }

    return result;
}
function nextGreaterElement(nums) {
  const result = Array(nums.length).fill(-1);
  const stack = [];

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()] = nums[i];
    }

    stack.push(i);
  }

  return result;
}

What Changed from the Base Template?

Fill the condition and the processing step

Base:

while (!stack.isEmpty() && /* order violated */) {
    // process j
}
while stack and /* order violated */:
    pass  # process j
while (!st.empty() && /* order violated */) {
    // process j
}
while (stack.length && /* order violated */) {
  // process j
}

Changed:

while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
    result[stack.pop()] = nums[i];
}
while stack and nums[stack[-1]] < num:
    result[stack.pop()] = num
while (!st.empty() && nums[st.top()] < nums[i]) {
    result[st.top()] = nums[i];
    st.pop();
}
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
  result[stack.pop()] = nums[i];
}

because a smaller top is waiting for a greater element, and nums[i] is that answer.

Next Greater = Base Template + Decreasing stack + Assign answer on pop.

Pattern 2: Daily Temperatures

Same stack of indices; the answer is a waiting DISTANCE instead of a value.

Daily Temperatures (Monotonic Decreasing Stack)

For each day, find how many days until a warmer temperature. A decreasing stack stores indices waiting for a warmer day; when a hotter day arrives it resolves (pops) every cooler day that was waiting.

Temps [73,74,75,71,72,76]. The stack holds indices whose answer is still unknown, with temperatures strictly DECREASING bottom→top. When nums[i] is hotter than the top, that top finally gets its answer (i - top). Each index is pushed and popped at most once, so it's O(n). The highlighted cell is the index being resolved/added; the array shows the answer filling in.

ARRAY VISUALIZER
Steps –
73
0
74
1
75
2
71
3
72
4
76
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        stack = []                  // indices, temps decreasing
                      
                        2
                        for i in 0..n-1:
                      
                        3
                          while stack and nums[i] > nums[stack.top]:
                      
                        4
                            j = pop(); answer[j] = i - j
                      
                        5
                          push(i)

Same stack — but the answer is how many days until a warmer temperature, not the value itself.

Code

public int[] dailyTemperatures(int[] temps) {
    int[] result = new int[temps.length];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < temps.length; i++) {
        while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
            int j = stack.pop();
            result[j] = i - j;
        }

        stack.push(i);
    }

    return result;
}
def daily_temperatures(temps: list[int]) -> list[int]:
    result = [0] * len(temps)
    stack = []

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)

    return result
vector<int> dailyTemperatures(vector<int>& temps) {
    vector<int> result(temps.size(), 0);
    stack<int> st;

    for (int i = 0; i < temps.size(); i++) {
        while (!st.empty() && temps[st.top()] < temps[i]) {
            int j = st.top(); st.pop();
            result[j] = i - j;
        }

        st.push(i);
    }

    return result;
}
function dailyTemperatures(temps) {
  const result = Array(temps.length).fill(0);
  const stack = [];

  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const j = stack.pop();
      result[j] = i - j;
    }

    stack.push(i);
  }

  return result;
}

What Changed from the Base Template?

Store distance instead of value

Base:

result[stack.pop()] = nums[i];
result[stack.pop()] = num
result[st.top()] = nums[i];
result[stack.pop()] = nums[i];

Changed:

int j = stack.pop();
result[j] = i - j;
j = stack.pop()
result[j] = i - j
int j = st.top(); st.pop();
result[j] = i - j;
const j = stack.pop();
result[j] = i - j;

because we need the gap between the two indices — this only works because the stack stores indices, not values.

Daily Temperatures = Base Template + Answer as index distance.

Pattern 3: Largest Rectangle in Histogram

Pops compute width × height — every bar’s best rectangle ends at a shorter neighbour.

Largest Rectangle in Histogram

Find the biggest rectangle that fits under a histogram. An increasing stack of indices tracks heights; when a shorter bar arrives it pops taller bars, and each popped bar's rectangle spans from the new top to the current index.

Bars [2,1,5,6,2,3] → area 10 (the 5×2 block). The stack holds indices with STRICTLY INCREASING heights. When a shorter bar arrives, popping a bar computes width = (current index) - (new stack top) - 1 and area = height × width. A sentinel keeps the final flush. The highlighted cell is the bar being resolved.

ARRAY VISUALIZER
Steps –
2
0
1
1
5
2
6
3
2
4
3
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        stack = []                  // indices, heights increasing
                      
                        2
                        for i in bars (+ sentinel 0):
                      
                        3
                          while h[i] < h[stack.top]:
                      
                        4
                            height = h[pop()]
                      
                        5
                            width = i - stack.top - 1
                      
                        6
                            best = max(best, height*width)

Flip to an increasing stack: when a shorter bar arrives, taller bars can’t extend further right — settle their area immediately.

Code

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int max = 0;

    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];

        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty()
                    ? i
                    : i - stack.peek() - 1;

            max = Math.max(max, height * width);
        }

        stack.push(i);
    }

    return max;
}
def largest_rectangle_area(heights: list[int]) -> int:
    stack = []
    max_area = 0

    for i in range(len(heights) + 1):
        h = 0 if i == len(heights) else heights[i]

        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area
int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int maxArea = 0;

    for (int i = 0; i <= heights.size(); i++) {
        int h = (i == heights.size()) ? 0 : heights[i];

        while (!st.empty() && h < heights[st.top()]) {
            int height = heights[st.top()];
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;

            maxArea = max(maxArea, height * width);
        }

        st.push(i);
    }

    return maxArea;
}
function largestRectangleArea(heights) {
  const stack = [];
  let max = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];

    while (stack.length && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0
        ? i
        : i - stack[stack.length - 1] - 1;

      max = Math.max(max, height * width);
    }

    stack.push(i);
  }

  return max;
}

What Changed from the Base Template?

Increasing stack + width calculation

Base:

while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
while stack and nums[stack[-1]] < num:
while (!st.empty() && nums[st.top()] < nums[i])
while (stack.length && nums[stack[stack.length - 1]] < nums[i])

Changed:

while (!stack.isEmpty() && h < heights[stack.peek()])
while stack and h < heights[stack[-1]]:
while (!st.empty() && h < heights[st.top()])
while (stack.length && h < heights[stack[stack.length - 1]])

because a shorter bar ends the reach of every taller bar on the stack.

Sentinel flush at the end

Added:

int h = (i == heights.length) ? 0 : heights[i];
h = 0 if i == len(heights) else heights[i]
int h = (i == heights.size()) ? 0 : heights[i];
const h = i === heights.length ? 0 : heights[i];

because the final 0 pops every remaining bar so no area is left uncounted.

The stack top after popping is each bar’s previous smaller element, giving the width:

width = i - previousSmallerIndex - 1

Histogram = Base Template + Increasing stack + Height × Width + Sentinel flush.

Monotonic Stack Pattern Evolution

Base Monotonic Stack
    ↓
Next Greater Element
    (+ decreasing stack + assign answer on pop)
    ↓
Daily Temperatures
    (+ answer as index distance)
    ↓
Largest Rectangle in Histogram
    (+ increasing stack + width calc + sentinel flush)

Common Mistakes

Storing values when you need positions.

Any question about distance, span, or width must push indices:

// Wrong — value alone can't recover distance or position
Stack<Integer> values;

// Correct
Stack<Integer> indices;
# Wrong
stack.append(num)

# Correct
stack.append(i)
// Wrong
stack<int> values;

// Correct
stack<int> indices;
// Wrong
stack.push(num);

// Correct
stack.push(i);

Wrong comparison direction.

nums[top] < current pops smaller → next greater. For next smaller, flip it to nums[top] > current.

Pick < or <= deliberately — it decides how duplicates are grouped.

Forgetting the default answer.

Elements never resolved keep their initial fill:

Arrays.fill(result, -1);  // or new int[n] for 0 defaults
result = [-1] * n  # or [0] * n
vector<int> result(n, -1);  // or vector<int> result(n, 0)
const result = Array(n).fill(-1); // or .fill(0)

Forgetting the histogram sentinel.

Without the final h = 0 pass, bars still on the stack are never settled and their areas are lost.

Recognition Cheat Sheet

If you see…Think…
Next/previous greaterDecreasing stack
Next/previous smallerIncreasing stack
Days/span until bigger/smallerMonotonic stack + distances
Largest rectangle / area of barsIncreasing stack + width calc

My Private Notes

Notes are auto-saved locally to this device.