Monotonic Stack Explained: How It Cuts Array Problem Time from O(n²) to O(n)

A monotonic stack is a data structure that maintains elements in strictly increasing or decreasing order, popping values whenever a new element breaks that order. This property makes it highly effective for array problems like 'Next Greater Element' and 'Largest Rectangle in Histogram,' reducing brute-force O(n²) solutions to linear O(n) time. The efficiency comes from the guarantee that each element is pushed and popped at most once, keeping total work proportional to array size. For the Next Greater Element problem, a decreasing stack is used to map each number to its next greater value, with leftover stack elements assigned -1 since no greater element exists for them. A common pitfall is forgetting to clear remaining stack elements at the end, which leaves the result map incomplete.