Skip to main content Link Search Menu Expand Document (external link)

Largest rectangle under an histogram

You are given an histogram and want to identify the area of the largest rectangle that fits under the histogram.

There is a solution in linear time using a stack. There is also a divide-and-conquer solution that we describe here.

On range $[l, r]$:

  • Find the minimum $m$
  • One rectangle candidate is $m \times (r - l + 1)$
  • Other rectangle candidates are recursively computed on the left and right of the minimum.

So the complexity overall verifies: \(T(n) = 2T(\frac{n}2) + f(n)\) where $f(n)$ is the cost of finding the minimum over an interval of length $n$.

Finding the minimum efficiently over a range

This task can be done:

Overall complexity

  1. If $f(n) = O(n)$, master theorem says complexity is $T(n) = \Theta(n \log n)$.
  2. If $f(n) = O(1)$, master theorem says complexity is $T(n) = \Theta(n)$.
  3. If $f(n) = O(\log n)$, well master theorem can’t be used; we can use instead a generalization called the Akra-Bazzi theorem (1998) with $p = 1, g(x) = \log x$:
\[\begin{align} T(x) & = \Theta\left(x\left(1 + \int_1^x \frac{g(u)}{u^2} du\right)\right)\\ & = \Theta\left(x\left(1 + \left[- \frac{\log x + 1}{x} + 1\right]\right)\right)\\ & = \Theta(2x - \log(x)) & = O(x). \end{align}\]