Histogram Puzzle: Brute Force

I am going to outline the brute force method of solving the histogram puzzle. This is not a terribly smart way to solve the problem, but at least it forces us to parse the problem.

As I will comment later, it is not completely without merits, either.

Let "i" and "j" be two indices which run from 1 to N. Given a pair (i, j), a unique rectangle (with the maximum possible area, given the indices) that is inscribed within the histogram can be identified.

In the figure above, if i = 2, and j = 3, this rectangle has dimensions 2*4. Similarly if i = 3, and j = 6, this rectangle has dimensions of 4*2. Or more generally (j - i + 1) * MinHeight(i, j), where MinHeight(i, j) is the minimum height of columns between i and j.

If maxRect represents the rectangle with the maximum area, h(i) the height of column i, then one can write an algorithm that looks something like:

maxRect = max{h(i)}     # initialize = tallest column

for i = 1 to N-1

  minHeight(i) = h(i)   # between i and current "j"

  for j = i+1 to N

    minHeight(i) = min(h(j), minHeight(i))

    area         = (j - i + 1) * minHeight(i)

    if(area > maxRect.area)

      maxRect = Rect(i, j)   # rectangle(i,j)

    endif

  endfor

endfor

This is an order O(N^2) algorithm, which is not terribly impressive. We can do much better, at least O(N log N).

However, before we write this off as a bad algorithm, I want to point out three redeeming features.

One, its memory footprint is small. Two, the algorithm is eminently "parallelizable". And three, it is simple to understand and maintain.

So in a world with different constraints, it may still have a chance.