We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Keep the stack increasing or decreasing, and popping becomes the moment you have found an element's next greater or smaller neighbour - the whole scan stays O(n). It is the standard answer to daily-temperatures, largest-rectangle-in-histogram, and trapping-rain-water. Genuinely hard to invent under interview pressure, which is exactly why it is worth recognising cold.
"Next greater/smaller element", or a maximum rectangle/area over a histogram.
7 problems. Each one runs in an in-browser editor against real test cases, with hints and a worked solution.
The patterns cheat sheet covers all of these in one page - what each one looks like in a problem statement, and the template that follows.