Watch 10 video solutions for Largest Rectangle in Histogram, a hard level problem involving Array, Stack, Monotonic Stack. This walkthrough by NeetCode has 387,126 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |