Largest Rectangle in Histogram
Recognize the pattern
Brute force idea
If you approach Largest Rectangle in Histogram in the most literal way possible, you get this: For each bar, expand left and right to find the rectangle. Each bar re-scans for boundaries. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
Better approach
A calmer way to see Largest Rectangle in Histogram is this: Monotonic increasing stack: for each bar, pop all taller bars (they've found their right boundary). The rectangle height is the popped bar, width extends from the new stack top to the current index. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Key invariant
The compass for Largest Rectangle in Histogram is this: The stack holds bar indices in increasing height order. When a shorter bar arrives, all taller bars on the stack have found their right boundary — calculate their rectangles before pushing the shorter bar. As long as that statement keeps holding, you can trust the steps built on top of it.
Watch out for
One easy way to drift off course in Largest Rectangle in Histogram is this: Not processing remaining bars after the loop — bars still on the stack haven't found a right boundary, so their right boundary is the array end. The fix is usually to return to the meaning of each move, not just the steps themselves.