Stacks and Monotonic Structures
Turning boundaries into widths
The hardest stack problem in the set, and it is the span formula you already wrote.
The reframe that does the work
Given bars of varying heights standing side by side, find the largest rectangle that fits inside them. The rectangle may span several bars and is limited by the shortest bar it covers.
Trying every pair of endpoints is O(n squared). The reframe is to stop thinking about rectangles and think about bars: every candidate rectangle has some shortest bar, so it is enough to ask, for each bar, what is the widest rectangle whose height is exactly that bar.
Why it works
The width of a bar's rectangle
A rectangle of a bar's height extends left until it meets something shorter, and right until it meets something shorter. Those are the previous-smaller and next-smaller boundaries you built in the monotonic stack lab.
With both boundaries exclusive, the width is next_smaller - previous_smaller - 1, which is the span formula from that lab, unchanged. The area is that width times the bar's height, and the answer is the largest over all bars.
Below, both boundary arrays are given rather than computed, so that the only thing on show is what they turn into. Producing them is the two stack passes you already know how to write.
Tip
Write the three-pass version
Two stack passes for the boundaries and one arithmetic pass over them, each a loop you have already written, and the whole thing is O(n). There is a well-known single-pass version that computes the width at the moment of the pop, and it is shorter and considerably easier to get wrong.
Offer the three-pass version first. If asked to tighten it, explain that when a bar is popped, the bar arriving now is its next-smaller boundary and the bar left underneath is its previous-smaller boundary, so the width is available right then. That sentence is the whole single-pass trick.
Gotcha
Equal heights and the strictness of the comparison
With >= in the pop condition, a bar with an equal-height neighbor treats that neighbor as a boundary, so its computed width is too short. That sounds like a bug and does not change the answer, because the other bar of the equal pair computes the full width and wins.
It is worth knowing that this is safe rather than discovering it by accident. If you switch to a strict comparison you must check the reasoning again, since which of the equal bars gets the full width changes.
Tip
The sentinel trick
Single-pass versions often append a zero-height bar at the end. Since nothing is shorter than zero, it forces every remaining bar off the stack and resolves them without a separate cleanup loop after the main one.
Sentinels are a general tidiness device: add an artificial element that makes the boundary case behave like the ordinary case. When you use one, say so, because a reader who has not spotted it will think the loop is missing its cleanup.
Cost of the two-pass version
Time and space for largest_rectangle_two_pass on n bars.
Time
Space
Largest Rectangle In Histogram
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.