84. Largest Rectangle In Histogram - Explanation

Description

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Note: This chart is known as a histogram.

Example 1:

Input: heights = [7,1,7,2,2,4]

Output: 8

Example 2:

Input: heights = [1,3,7]

Output: 7

Constraints:

1 <= heights.length <= 1000.
0 <= heights[i] <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A rectangle has a height and a width. Can you visualize how rectangles are formed in the given input? Considering one bar at a time might help. We can try to form rectangles by going through every bar and current bar's height will be the height of the rectangle. How can you determine the width of the rectangle for the current bar being the height of the rectangle? Extending the current bar to the left and right might help determine the rectangle's width.

Hint 2

For a bar with height h, try extending it to the left and right. We can see that we can't extend further when we encounter a bar with a smaller height than h. The width will be the number of bars within this extended range. A brute force solution would be to go through every bar and find the area of the rectangle it can form by extending towards the left and right. This would be an O(n^2) solution. Can you think of a better way? Maybe precomputing the left and right boundaries might be helpful.

Hint 3

The left and right boundaries are the positions up to which we can extend the bar at index i. The area of the rectangle will be height[i] * (right - left + 1), which is the general formula for height * width. These boundaries are determined by the first smaller bars encountered to the left and right of the current bar. How can we find the left and right boundaries now? Maybe a data structure is helpful.

Hint 4

We can use a stack with a monotonically strictly increasing nature, but instead of storing values, we store indices in the stack and perform operations based on the values at those indices. The top of the stack will represent the smaller bar that we encounter while extending the current bar. To find the left and right boundaries, we perform this algorithm from left to right and vice versa, storing the boundaries. Then, we iterate through the array to find the area for each bar and return the maximum area we get.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

For every bar, we try to treat it as the shortest bar in the rectangle.
To find how wide this rectangle can extend, we look left and right until we hit a bar shorter than the current one.
The width between these two boundaries gives the largest rectangle where this bar is the limiting height.
We repeat this for every bar and keep track of the maximum rectangle found.

Algorithm

Let maxArea store the largest rectangle found.
For each index i:
- Let height be the height of the current bar.
- Expand to the right until you find a bar shorter than height.
- Expand to the left while bars are not shorter than height.
- Compute the width between the boundaries.
- Update maxArea with height * width.
Return maxArea.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        maxArea = 0

        for i in range(n):
            height = heights[i]

            rightMost = i + 1
            while rightMost < n and heights[rightMost] >= height:
                rightMost += 1

            leftMost = i
            while leftMost >= 0 and heights[leftMost] >= height:
                leftMost -= 1

            rightMost -= 1
            leftMost += 1
            maxArea = max(maxArea, height * (rightMost - leftMost + 1))
        return maxArea

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Divide And Conquer (Segment Tree)

Intuition

A large rectangle in the histogram must have some bar as its shortest bar.
If we know the index of the minimum height bar in any range, then:

The largest rectangle that uses that bar as the limiting height spans the entire range.
Anything larger must lie entirely on the left or entirely on the right of that bar.

So we can solve the problem with a divide and conquer idea:

In a given range [L, R], find the index of the smallest bar.
Compute:
- The area using this bar across the whole range.
- The best area entirely in [L, minIndex - 1].
- The best area entirely in [minIndex + 1, R].
The answer for [L, R] is the maximum of those three.

To find the index of the minimum height quickly for any range, we use a segment tree built on heights. It supports “min index in range” queries in O(log n) time, which makes the whole divide-and-conquer efficient.

Algorithm

Build a segment tree over the heights array:
- Each node stores the index of the minimum height in its segment.
Define a recursive function solve(L, R):
- If L > R, return 0.
- If L == R, return heights[L] (only one bar).
- Use the segment tree to find minIndex = index of the smallest bar in [L, R].
- Compute:
  - area_with_min = heights[minIndex] * (R - L + 1)
  - area_left = solve(L, minIndex - 1)
  - area_right = solve(minIndex + 1, R)
- Return max(area_with_min, area_left, area_right).
The final answer is solve(0, n - 1) where n is the number of bars.

class MinIdx_Segtree:
    def __init__(self, N, A):
        self.n = N
        self.INF = int(1e9)
        self.A = A
        while (self.n & (self.n - 1)) != 0:
            self.A.append(self.INF)
            self.n += 1
        self.tree = [0] * (2 * self.n)
        self.build()

    def build(self):
        for i in range(self.n):
            self.tree[self.n + i] = i
        for j in range(self.n - 1, 0, -1):
            a = self.tree[j << 1]
            b = self.tree[(j << 1) + 1]
            if self.A[a] <= self.A[b]:
                self.tree[j] = a
            else:
                self.tree[j] = b

    def update(self, i, val):
        self.A[i] = val
        j = (self.n + i) >> 1
        while j >= 1:
            a = self.tree[j << 1]
            b = self.tree[(j << 1) + 1]
            if self.A[a] <= self.A[b]:
                self.tree[j] = a
            else:
                self.tree[j] = b
            j >>= 1

    def query(self, ql, qh):
        return self._query(1, 0, self.n - 1, ql, qh)

    def _query(self, node, l, h, ql, qh):
        if ql > h or qh < l:
            return self.INF
        if l >= ql and h <= qh:
            return self.tree[node]
        a = self._query(node << 1, l, (l + h) >> 1, ql, qh)
        b = self._query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh)
        if a == self.INF:
            return b
        if b == self.INF:
            return a
        return a if self.A[a] <= self.A[b] else b

class Solution:
    def getMaxArea(self, heights, l, r, st):
        if l > r:
            return 0
        if l == r:
            return heights[l]
        minIdx = st.query(l, r)
        return max(max(self.getMaxArea(heights, l, minIdx - 1, st),
                       self.getMaxArea(heights, minIdx + 1, r, st)),
                   (r - l + 1) * heights[minIdx])

    def largestRectangleArea(self, heights):
        n = len(heights)
        st = MinIdx_Segtree(n, heights)
        return self.getMaxArea(heights, 0, n - 1, st)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Stack

Intuition

For each bar, we want to know how far it can stretch left and right before bumping into a shorter bar.
That distance tells us the widest rectangle where this bar is the limiting height.
To efficiently find the nearest smaller bar on both sides, we use a monotonic stack that keeps indices of bars in increasing height order.
This lets us compute boundaries in linear time instead of checking outward for every bar.

Algorithm

Use a stack to find, for each index i, the nearest smaller bar on the left:
- If the current bar is shorter than the bar on top of the stack, pop until this is no longer true.
- The top of the stack becomes the left boundary.
- If the stack is empty, no smaller bar exists → left boundary is -1.
Repeat the same process from right to left to find the nearest smaller bar on the right:
- If no smaller bar exists, the right boundary is n.
For each bar:
- Expand between the boundaries and compute its max rectangle:
  height[i] * (right - left - 1)
Return the largest area found.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stack = []

        leftMost = [-1] * n
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                leftMost[i] = stack[-1]
            stack.append(i)

        stack = []
        rightMost = [n] * n
        for i in range(n - 1, -1, -1):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                rightMost[i] = stack[-1]
            stack.append(i)

        maxArea = 0
        for i in range(n):
            leftMost[i] += 1
            rightMost[i] -= 1
            maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1))
        return maxArea

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Stack (One Pass)

Intuition

We want, for each bar, the widest area where it can act as the shortest bar.
With a single pass and a stack, we can do this on the fly:

We keep a stack of bars in increasing height order, each stored with the earliest index where that height can start.
When we see a new bar that is shorter than the top of the stack, it means the taller bar on top can’t extend further to the right.
- So we pop it and compute the area it could cover.
The new shorter bar can start from as far left as the popped bar’s start index, so we reuse that index.
After the pass, we compute areas for any bars still in the stack, extending them to the end.

Each bar is pushed and popped at most once, giving an efficient, one-pass solution.

Algorithm

Initialize:
- an empty stack to store pairs (start_index, height),
- maxArea = 0.
Traverse the histogram from left to right with index i and height h:
- Set start = i.
- While the stack is not empty and the top height is greater than h:
  - Pop (index, height) from the stack.
  - Update maxArea with height * (i - index).
  - Set start = index (the new bar can start from here).
- Push (start, h) onto the stack.
After the loop, process remaining bars in the stack:
- For each (index, height) in the stack:
  - Update maxArea with height * (n - index), where n is the total number of bars.
Return maxArea.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []  # pair: (index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Stack (Optimal)

Intuition

We want, for every bar, to know how wide it can stretch while still being the shortest bar in that rectangle.

A monotonic stack helps with this:

We keep a stack of indices where the bar heights are in increasing order.
As long as the next bar is taller or equal, we keep pushing indices.
When we see a shorter bar, it means the bar on top of the stack can’t extend further to the right:
- We pop it and treat it as the height of a rectangle.
- Its width goes from the new top of the stack + 1 up to the current index − 1.

To make sure every bar eventually gets popped and processed, we run the loop one extra step with a “virtual” bar of height 0 at the end.
Each bar is pushed and popped at most once, so this is both optimal and clean.

Algorithm

Initialize:
- maxArea = 0
- an empty stack to store indices of bars (with heights in increasing order).
Loop i from 0 to n (inclusive):
- While the stack is not empty and either:
  - i == n (we’re past the last bar, acting like height 0), or
  - heights[i] is less than or equal to the height at the top index of the stack:
    - Pop the top index; let its height be h.
    - Compute the width:
      - If the stack is empty, width = i (it extends from 0 to i - 1).
      - Otherwise, width = i - stack.top() - 1.
    - Update maxArea with h * width.
- Push the current index i onto the stack.
After the loop, maxArea holds the largest rectangle area. Return it.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        maxArea = 0
        stack = []

        for i in range(n + 1):
            while stack and (i == n  or heights[stack[-1]] >= heights[i]):
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                maxArea = max(maxArea, height * width)
            stack.append(i)
        return maxArea

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$