LeetCode 84 Largest Rectangle in Histogram - Why Naive Fails

For each bar, expand left and right to find how far you can go while heights stay >= current bar's height. Calculate area.

For bar at index i, you might scan almost the entire array to find the boundaries. That's $O(n)$ per bar, $O(n^2)$ total.

Can you precompute the boundaries for all bars efficiently?