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.

1heights = [2, 1, 5, 6, 2, 3]2 3# Nearest strictly shorter bar on each side, exclusive, from the earlier lab.4previous_smaller = [-1, -1, 1, 2, 1, 4]5next_smaller = [1, 6, 4, 4, 6, 6]6 7for i, height in enumerate(heights):8    width = next_smaller[i] - previous_smaller[i] - 19    print(f"bar {i}, height {height}, spans {width} -> area {width * height}")

The bar of height 1 spans everything, and the tallest bar spans almost nothing.

Complexity· 5 min

Cost of the two-pass version

Time and space for largest_rectangle_two_pass on n bars.

Problem· 35 min

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.

CodeGround