NUHMAN.com

Introduction

LeetCode 84: Largest Rectangle in Histogram is a classic and challenging problem. It asks you to find the area of the largest rectangle that can be formed in a histogram represented as an array of heights.

This problem is best solved using a monotonic stack, and it's an excellent exercise in combining data structures with algorithmic thinking.

Problem Statement

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:

go

Input: heights = [2,1,5,6,2,3]
Output: 10

Explanation: The largest rectangle is of height 5 and 6 with width 2: area = 5*2 = 10

Approach: Monotonic Stack

Why a stack?

We use a monotonic increasing stack to keep track of bar indices in increasing height order. The idea is:

• When a smaller height is encountered, we pop from the stack and calculate area using the popped height as the smallest bar.
• This ensures we only calculate when the rectangle can no longer be extended to the right.

Algorithm Steps:

1. Append 0 to the end of the heights array to flush out remaining stack elements.
2. Use a stack to store indices of bars.
3. Iterate through heights:

• If the current height is greater or equal to the height at stack top, push index.
• Otherwise, pop from the stack and calculate area with the popped height:
• Width is (current index - stack top index - 1)

1. Track and return the maximum area found.

Go Implementation

go

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0) // Sentinel to flush stack

    for i := 0; i < len(heights); i++ {
        for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            height := heights[top]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }

            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }

    return maxArea
}

Explanation

• The stack holds indices of bars in increasing height.
• When a shorter bar is found, we:
• Pop the last bar.
• Calculate the width of the rectangle.
• Calculate and update the area.
• The sentinel 0 at the end forces all remaining bars to be processed.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where n is the number of bars in the histogram.

Edge Cases

• Empty heights array → return 0.
• All bars of the same height → area = height × number of bars.
• Strictly increasing or decreasing heights → handled via stack logic.

Conclusion

LeetCode 84 is a tough but rewarding problem that helps you master stack usage for range-based area calculation. It's particularly useful in solving 2D variations like Maximal Rectangle.

Using a monotonic stack is the key technique here—efficient and elegant.