Monotonic Stack (Next Greater Element)

Medium

Use a monotonic stack to find each element's Next Greater Element in O(n). Push indices onto a stack; when a new value is greater than the value at the stack top, pop it and fill that position's answer.

📊 Complexity

Type	Value
Best	O(n)
Average	O(n)
Worst	O(n)
Space	O(n)

🏷️ Tags

StackMonotonic StackNext Greater ElementO(n)

📖 Introduction

A monotonic stack is a stack maintained so its elements (usually indices) always stay in increasing or decreasing order. For Next Greater Element, we push indices while keeping the stored values in decreasing order from bottom to top (monotonically decreasing).

1/21

🚀Start Monotonic Stack

We find each element's Next Greater Element. The stack holds indices that haven't found an answer yet; when a larger new element arrives, we pop and fill answers. result starts all -1.

Monotonic Stack (Next Greater Element)

Medium

Monotonic Stack (Next Greater Element)

📊 Complexity

Type	Value
Best	O(n)
Average	O(n)
Worst	O(n)
Space	O(n)

🏷️ Tags

StackMonotonic StackNext Greater ElementO(n)

📖 Introduction

1/21

🚀Start Monotonic Stack

We find each element's Next Greater Element. The stack holds indices that haven't found an answer yet; when a larger new element arrives, we pop and fill answers. result starts all -1.

🚀Start Monotonic Stack