Skip to content

84. Largest Rectangle in HistogramΒΆ

Problem Link

largest rectangle in histogram

Largest Rectangle in histogram would be selected from the largest rectangles using each individual bars. Maximum rectangle for each bar can found by limiting height of rectangle to current bar, and finding the widest width possible to the left and right.

The width for a given bar is bounded by the nearest bar with a smaller height on both sides. Any taller or equal bar can be included in the rectangle, but a smaller bar stops the expansion. A brute-force approach for finding this width could be expanding left and right for every bar to find these boundaries, but doing this repeatedly for all bars results in \(O(n^2)\) time complexity with constant extra space.

We can optimize this by precomputing the indices of the nearest smaller bar for each index in \(O(n)\) time using a stack. The idea is to maintain a monotonic increasing stack of indices, which allows us to efficiently find nearest smaller elements.

Pseudocode

Maintain a stack where the heights corresponding to indices are in increasing order. For each index:

  • While the stack is not empty and the height at the stack's top index is greater than or equal to the current height, pop from the stack.
  • After popping, the new top (if it exists) represents the nearest smaller bar.
  • Store this index in an auxiliary array.
  • Push the current index onto the stack so it can serve as a boundary for future bars.

This approach gives us \(O(n)\) time and space complexity

Runtime Complexity

Time: \(O(n)\), single pass on array, for precomputing arrays and max area

Space: \(O(n)\), from left, right arrays and stack which can grow upto size of \(heights\) 

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        lp = [-1]*n
        stk = []
        for i in range(n):
            while stk and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if stk:
                lp[i] = stk[-1]
            stk.append(i)

        rp = [n]*n
        stk = []
        for i in range(n-1, -1, -1):
            while stk and heights[i] <= heights[stk[-1]]:
                stk.pop()
            if stk:
                rp[i] = stk[-1]
            stk.append(i)

        result = 0
        for i, height in enumerate(heights):
            area = height * (rp[i] - lp[i] + 1)
            result = max(result, area)

        return result

func getIntArray(size int, def int) []int {
    arr := make([]int, size)
    for i := range arr {
        arr[i] = def
    }
    return arr
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    left := getIntArray(n, -1)
    var stk []int
    for i := 0; i < n; i++ {
        for len(stk) != 0 && heights[i] <= heights[stk[len(stk)-1]] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) != 0 {
            left[i] = stk[len(stk)-1]
        }
        stk = append(stk, i)
    }

    right := getIntArray(n, n)
    stk = []int{}
    for i := n - 1; i >= 0; i-- {
        for len(stk) != 0 && heights[i] <= heights[stk[len(stk)-1]] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) != 0 {
            right[i] = stk[len(stk)-1]
        }
        stk = append(stk, i)
    }

    var result, area int
    for i := range heights {
        area = heights[i] * (right[i] - left[i] - 1)
        result = max(result, area)
    }
    return result
}