Largest Rectangle in Histogram

Reported in interviews at Citadel Pinterest

Problem statement

Given an array of non-negative integers heights where each element represents the height of a bar in a histogram (all bars have width 1), find the area of the largest rectangle that can be formed within the histogram.

Your solution must run in $O(n)$ time and $O(n)$ space using a monotonic stack. Additionally:

  1. Explain how sentinel values simplify the implementation.
  2. Explain how to handle bars of equal height correctly.
  3. Show how to return the witness interval $[i, j]$ (the left and right boundaries of the optimal rectangle).

Constraints:

  • $1 \le \text{heights.length} \le 10^5$
  • $0 \le \text{heights}[i] \le 10^4$

Example 1:

  • Input: heights = [2, 1, 5, 6, 2, 3]
  • Output: 10
  • Explanation: The largest rectangle has area $10$ (spanning bars at indices 2 and 3, with height 5 and width 2).

Example 2:

  • Input: heights = [2, 4]
  • Output: 4
Show hint

For a rectangle whose height equals one particular bar, what limits how far it can extend to either side?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems