Why does the stack hold indices instead of heights?

The width of a popped bar's rectangle comes from positions: i - left - 1, where left is the index now on top of the stack. A height alone cannot tell you where the bar stood, while heights[top] gives the height back from an index whenever you need it.

Should the comparison be >= or > when popping?

Both give the right answer. With >=, an equal bar pops the earlier one, whose width is then too short, but the later equal bar keeps the shared left boundary and gets the full width when it is popped. With >, equal bars stay on the stack together and the last one popped scores the run. Pick one and use it in every loop of the solution.

Can I append 0 to heights instead of the i < n check?

Yes: heights.append(0) before the loop gives the same flush at the end with a shorter loop body. It changes the caller's list, though, so for h in heights + [0] (a copy) or the index check shown here is the safer habit when the list is not yours.

Is the brute force fast enough in Python?

At this size bound, yes: about two million inner steps, which plain CPython finishes in well under a second. The running minimum is what keeps it at O(n²); recomputing min(heights[i:j + 1]) for every pair would be O(n³) and far too slow.

How does this relate to the largest rectangle of 1s in a binary matrix?

That problem reduces to this one. Walk the matrix row by row, keeping a list where each column holds how many 1s stand directly above and including the current cell (reset to 0 on a 0). Each row's list is a histogram, and the best largest_rectangle_area over all rows is the answer, in O(rows × cols) time.

Largest Rectangle in Histogram: Solution Explained in 15 Languages

Q: Can I append 0 to heights instead of the i < n check?

Yes: heights.append(0) before the loop gives the same flush at the end with a shorter loop body. It changes the caller's list, though, so for h in heights + [0] (a copy) or the index check shown here is the safer habit when the list is not yours.

Q: Is the brute force fast enough in Python?

At this size bound, yes: about two million inner steps, which plain CPython finishes in well under a second. The running minimum is what keeps it at O(n²); recomputing min(heights[i:j + 1]) for every pair would be O(n³) and far too slow.

Q: How does this relate to the largest rectangle of 1s in a binary matrix?

That problem reduces to this one. Walk the matrix row by row, keeping a list where each column holds how many 1s stand directly above and including the current cell (reset to 0 on a 0). Each row's list is a histogram, and the best largest_rectangle_area over all rows is the answer, in O(rows × cols) time.

largest_rectangle_area.py

Python 3.14

Not run yet

+ 8 hidden

Input

heights = [2, 4, 5, 3, 1, 3]

Expected

The bars 4, 5, 3 at indices 1 to 3 are all at least 3 tall, so a rectangle of height 3 and width 3 fits: 3 × 3 = 9. The tallest bar alone gives only 5.