Monotonic Stack

DSA · Stacks and Queues

Theory

A monotonic stack keeps its elements in increasing or decreasing order. When a new element would break the order, elements are popped until the order is restored; at that moment each popped element has found its "next greater" (or smaller) element. Every element is pushed and popped at most once, so the whole scan is O(n).

Why we use it

It answers "next greater/smaller element" style questions in linear time instead of O(n²).

When to use it

Use it for next greater element, daily temperatures, stock span, largest rectangle in a histogram, and trapping rain water.

How it works

  1. For each element x
  2. Stack not empty and top < x? Yes: Pop top: x is its next greater element. No: Push x.
  3. Repeat the check
  4. Remaining items have no next greater element

Syntax

stack = []                     # holds indexes
for i, x in enumerate(arr):
    while stack and arr[stack[-1]] < x:
        j = stack.pop(); answer[j] = x   # next greater for j
    stack.append(i)

Example

def next_greater(nums):
    answer = [-1] * len(nums)
    stack = []
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            answer[stack.pop()] = nums[i]
        stack.append(i)
    return answer

def days_until_warmer(temps):
    wait = [0] * len(temps)
    stack = []
    for i in range(len(temps)):
        while stack and temps[stack[-1]] < temps[i]:
            j = stack.pop()
            wait[j] = i - j
        stack.append(i)
    return wait

print(next_greater([4, 5, 2, 25, 7, 8]))
print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic