Largest Rectangle Under Skyline

Tags

Largest Rectangle Under Skyline

Category

Stacks

Difficulty

Hard

Problem Statement

Given an array of non-negative integers representing the heights of buildings in a histogram (each building has width 1), find the area of the largest rectangle that can be formed within the histogram. The rectangle must be axis-aligned and fit entirely under the skyline.

Intuition

For each bar, we want to know how far it can extend to the left and right while remaining the shortest bar (i.e., while its height is the limiting factor). A monotonic stack efficiently computes this. By maintaining a stack of bar indices in increasing height order, each time we encounter a bar shorter than the stack's top, we can calculate the maximum rectangle for the popped bar — because we now know its right boundary (the current bar) and its left boundary (the new top of the stack).

Approach

  1. Initialize an empty stack and maxArea = 0.
  2. Iterate through the buildings with index i from 0 to n: a. Use height 0 at index n as a sentinel to flush the stack. b. While the stack is not empty and heights[i] < heights[stack.top()]:
    • Pop the top index as poppedIndex.
    • The height of the rectangle is heights[poppedIndex].
    • The width extends from the current stack top + 1 to i - 1. If the stack is empty, the width is i.
    • Compute area = height * width and update maxArea. c. Push i onto the stack.
  3. Return maxArea.

Pseudocode

function largestRectangleUnderSkyline(buildings):
    maxArea = 0
    stack = []

    for i from 0 to length(buildings):
        currentHeight = 0 if i == length(buildings) else buildings[i]

        while stack is not empty and currentHeight < buildings[stack.top()]:
            height = buildings[stack.pop()]
            if stack is empty:
                width = i
            else:
                width = i - stack.top() - 1
            maxArea = max(maxArea, height * width)

        stack.push(i)

    return maxArea

Time & Space Complexity

  • Time: O(n) — Each index is pushed and popped from the stack at most once.
  • Space: O(n) — For the stack, which can hold up to n indices.

Key Insights

  • The monotonic stack maintains indices of bars in strictly increasing height order. This invariant means that when a bar is popped, its left and right boundaries are immediately known.
  • The sentinel value (height 0 at the end) ensures all remaining bars in the stack are processed without special-case code after the loop.
  • The width calculation when the stack is empty means the popped bar was the shortest seen so far, so the rectangle extends from index 0 to i - 1.
  • This is one of the most important monotonic stack applications and forms the basis for the "maximal rectangle in a binary matrix" problem.

Edge Cases

  • Empty array: return 0.
  • All bars have the same height: the answer is height * n.
  • Strictly increasing heights: the largest rectangle is found when processing the final sentinel.
  • Strictly decreasing heights: each bar is processed immediately, and the widest rectangle is determined by the shortest bar.
  • Single bar: the answer is that bar's height.
  • Array with zeros: zeros act as natural separators between independent sub-histograms.

Linked mentions