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 are given an array where each element represents the height of a histogram bar. The goal is to find the largest rectangular area that can be formed using consecutive bars. The rectangle must use the full width of the selected bars and the minimum height among them.
Approach 1: Divide and Conquer (Average O(n log n), Worst O(n²) time, O(log n) space)
This approach mirrors the strategy used in problems like maximum subarray. For a given range, find the index of the minimum height bar. That bar becomes the limiting height of a rectangle spanning the entire range. Compute three candidates: rectangle using the minimum bar across the full width, best rectangle in the left subarray, and best rectangle in the right subarray. Recursively evaluate both halves and return the maximum. The method is intuitive but can degrade to O(n²) if the array is already sorted because the minimum element repeatedly splits the array unevenly.
Approach 2: Monotonic Stack Method (O(n) time, O(n) space)
This method uses a stack to maintain indices of histogram bars in increasing height order. While iterating through the array, push indices as long as heights keep increasing. When a smaller height appears, repeatedly pop from the stack because the popped bar can no longer extend further right. Calculate the area using the popped height as the smallest bar and the distance between the current index and the new stack top as the width. This stack is called a monotonic stack because heights remain ordered. Each bar is pushed and popped at most once, giving linear time complexity.
Recommended for interviews: The monotonic stack approach is what most interviewers expect. It demonstrates understanding of boundary expansion problems and efficient stack usage. The divide and conquer idea helps build intuition, but the O(n) stack solution shows stronger algorithmic optimization skills.
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.
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.
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 |
|---|---|---|---|
| Divide and Conquer | Average O(n log n), Worst O(n²) | O(log n) | Useful for conceptual understanding or when practicing recursive partitioning techniques |
| Monotonic Stack | O(n) | O(n) | Best general solution and the approach typically expected in coding interviews |
LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python • NeetCode • 387,126 views views
Watch 9 more video solutions →Practice Largest Rectangle in Histogram with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor