Stacks and next greater element

The monotonic stack: every element pushed once and popped once, so O(n) instead of O(n squared).

13 min read · Lesson 6 of 6 · Pro

The pattern

A monotonic stack keeps its contents in sorted order - always increasing, or always decreasing, from bottom to top. Before pushing a new element, you pop everything that would break the order.

Each element is pushed once and popped at most once. So even though there is a while loop inside a for loop, the total work is O(n). That "amortised" argument is the follow-up question, so be ready for it.

The stack holds elements that are still waiting for an answer. When a new element arrives that answers them, they pop and get their result.

The rest of this lesson is Pro

The free lessons of DSA Interview Patterns finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.