162. Largest Rectangular Area in a Histogram

Given n bars of a histogram with given heights (each of width 1, standing side by side), find the area of the largest rectangle that can be formed within the histogram's outline.

Input: The first line contains an integer n. The second line contains n space-separated integers representing the bar heights. Output: Print a single integer - the area of the largest rectangle in the histogram.

1 <= n <= 10^5

This is the foundational technique behind 'Maximum Size Rectangle of 1s in a Binary Matrix' (from the Arrays category), which reduces a 2D problem into a sequence of exactly this 1D histogram problem, row by row.

Given a histogram's bar heights, find the area of the largest rectangle that fits entirely within its outline. Brute force: Check every possible pair of left and right boundaries directly, finding the minimum height within that range and computing the resulting area - this costs O(n²) or worse, too slow for large histograms. Optimised: A monotonic stack of increasing heights lets each bar's MAXIMUM possible rectangle (using ITSELF as the limiting height) be computed exactly once, the moment a shorter bar forces it to be popped - the left and right boundaries for that rectangle are directly given by the current index and the new stack top, no need to re-scan for them.

For every bar, treat it as the shortest bar in some rectangle and expand left and right as far as possible while all bars in that range are at least as tall as it, then compute width times height for that bar's maximal rectangle. Taking the maximum over all bars gives the correct answer because the largest rectangle in the histogram must have its height equal to the height of some bar, and that bar must be the minimum-height bar spanning the rectangle's width. This is correct but requires, in the worst case, scanning almost the whole array for each of the n bars. Time: O(n^2) Space: O(1)

Scan the bars once while maintaining a stack of indices with increasing heights; whenever the current bar is shorter than the bar at the top of the stack, pop it and compute the rectangle it would form using the current index as its right boundary and the new stack top as its left boundary. Because the stack always holds bars in increasing height order, every bar is pushed and popped at most once, so each bar's maximal rectangle (bounded by the nearest shorter bar on each side) is computed in amortized constant time. This single linear pass finds the true maximum without ever re-examining a bar, making it the standard optimal solution. Time: O(n) Space: O(n)

Find the index of the minimum-height bar within the current range (using a segment tree built once for O(log n) range-minimum queries), compute the rectangle that spans the whole range at that minimum height, then recursively solve the left and right sub-ranges split at the minimum, taking the best of the three candidates. This works because the largest rectangle either uses the minimum bar across the whole range or lies entirely to one side of it, so recursing on both sides never misses the true optimum. Using a segment tree for the minimum query keeps each split cheap, giving noticeably better performance than the pairwise brute force. Time: O(n log n) Space: O(n)

1. Use a stack of indices, keeping bar heights in INCREASING order as you scan left to right. 2. When a SHORTER bar appears, pop taller bars off one at a time - for each popped bar, compute the rectangle IT could have formed, using the current index as the right boundary and the new stack top as the left boundary. 3. Push a virtual bar of height 0 at the very end to force-flush any bars still remaining on the stack.

Time: O(n) - each bar is pushed and popped from the stack at most once. Space: O(n) in the worst case, for the stack.

n = 1 (area equals that single height); strictly increasing or strictly decreasing heights; all bars the same height (area = n times that height); n up to 10^5 for performance.

This is one of the most classic and celebrated stack-based interview problems - be ready to explain precisely why popping a bar reveals its EXACT maximum rectangle (using it as the limiting height, bounded by the nearest shorter bars on each side).