Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 1050 <= heights[i] <= 104Problem Overview: You receive an array where each value represents the height of a bar in a histogram. The task is to compute the largest rectangular area that can be formed using consecutive bars. Each bar has width 1, so the challenge is identifying how far each bar can extend left and right while remaining the minimum height.
Approach 1: Monotonic Stack (O(n) time, O(n) space)
This approach uses a monotonic increasing stack to track bar indices while scanning the histogram from left to right. When the current bar height becomes smaller than the height at the stack top, the stack is popped and the popped bar is treated as the limiting height of a rectangle. The width is determined by the current index and the new stack top, giving the maximum span where that height is the minimum. Each index is pushed and popped at most once, which keeps the time complexity at O(n) with O(n) extra space for the stack.
The key insight: every bar acts as the smallest bar in some maximal rectangle. The stack helps identify the first smaller bar on both sides efficiently. This method is the industry-standard solution and appears frequently in problems involving stack, array, and monotonic stack patterns.
Approach 2: Divide and Conquer (Average O(n log n), Worst O(n^2), Space O(log n))
This strategy mirrors the logic used in maximum subarray style recursion. For any range of the histogram, find the index of the minimum height bar. The largest rectangle must be one of three possibilities: entirely in the left subarray, entirely in the right subarray, or spanning the entire range using the minimum height. Recursively compute the maximum area for the left and right segments and compare them with the area formed by the minimum bar.
The recursive depth averages O(log n) if the histogram is balanced, resulting in O(n log n) time. In the worst case (sorted heights), the recursion degenerates to O(n^2). Space usage comes from the recursion stack. This method is conceptually clean and demonstrates how global constraints can be split recursively, though it is slower than the stack-based approach.
Recommended for interviews: Interviewers expect the Monotonic Stack solution. It runs in linear time and shows strong understanding of stack-based boundary detection. Starting with the divide-and-conquer idea can show reasoning about the problem structure, but implementing the O(n) stack approach demonstrates mastery of histogram and range-boundary patterns commonly tested in technical interviews.
This approach utilizes a monotonic stack to efficiently track the heights of the histogram bars. By iterating through the array and maintaining a stack of indices, we can pop the stack whenever we find a shorter bar, calculate the area of the rectangle formed with the popped bar as the shortest.bar and update the maximum area if necessary. The stack helps to find the left and right boundaries for each bar to compute the area.
The C implementation uses a stack to keep track of histogram bar indices. As we iterate through the height array, when we find a smaller height or the end of the array, we calculate the area of rectangles with heights of bars represented by indices in the stack (as they become the limiting height). As a result, when popping from the stack, we know there cannot be a higher height on the left, hence our width is calculated by i - stack[top] - 1. The maximum rectangle area is then updated accordingly. Finally, the stack is freed to ensure no memory leaks.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of bars (height array length), since each bar is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack.
This approach is inspired by the algorithm for finding the maximum subarray sum, with the core idea to exploit the properties of minimal elements acting as the constraints. Here, smaller segments of the array are divided to compute maximum rectangular areas separately and then to combine comprehensive results. It works optimally when the heights array is transformed to assist binary division, allowing recursive calls to determine the peak areas between and within divisions.
The C code employs a recursive divide and conquer methodology, recursively finding the minimum height in each segment as a pivot for maximal rectangle widths. It calculates areas recursively, thereby considering left and right segments separated by previously determined minimal height - or "pivot" - as the rectangular height at that segment.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), with potential for worse case involving complete traversal checks.
Space Complexity: O(n) for recursive calls.
| Approach | Complexity |
|---|---|
| Monotonic Stack Method | Time Complexity: O(n), where n is the number of bars (height array length), since each bar is pushed and popped from the stack at most once. |
| Divide and Conquer | Time Complexity: O(n^2), with potential for worse case involving complete traversal checks. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Monotonic Stack | O(n) | O(n) | Best general solution. Linear scan with stack efficiently finds previous and next smaller bars. |
| Divide and Conquer | O(n log n) average, O(n^2) worst | O(log n) | Useful for understanding the recursive structure of the problem or when exploring segment-based reasoning. |
Coding Interview Problem: Largest Rectangle in a Histogram • Jackson Gabbard • 310,605 views views
Watch 9 more video solutions →Practice Largest Rectangle in Histogram with our built-in code editor and test cases.
Practice on FleetCode