Largest rectangle in histogram problem

The problem is to find the largest rectangle under a histogram.

This question is the last question from 2003/2004 ACM International Collegiate Programming Contest, Univ. of Ulm Local Contest. It's one of the 2 hard ones in this question set. See the problem description and the solution.

The naive algorithm is for each column, scan all the other columns to find max rectangle. This is O(n^2). O(n*log(n)) solution exists, for example, using order statistic trees. O(n) solution also exists, for example, using a stack. See above link for the solutions.

The O(n) solution using a stack is not difficult to code. About 50 lines of C++ code will do. See below.

#include <iostream>
#include <stack>
using namespace std;

void getMax(int hist[], stack<int> * s, int right, int & max) {
  int i = s->top();
  int height = hist[i];
  s->pop();
  int left = (s->size() > 0) ? s->top() : -1;
  int area = height * (right - left);
  if (area > max) max = area;
}

void doHist(int hist[], int len) {
  stack<int> * s = new stack<int>;
  int i, max, top_v, right;

  max = 0;
  for (i = 0; i < len; i ++) {
    if (s->size() == 0) {
      s->push(i);
      continue;
    }

    top_v = hist[s->top()];
    if (hist[i] > top_v) {
      s->push(i);
    } else if (hist[i] < top_v) {
      while (s->size() > 0 && hist[i] < hist[s->top()]) {
        getMax(hist, s, i - 1, max);
      }
      s->push(i);
    }
  }

  while (s->size() > 0) getMax(hist, s, i - 1 , max);

  cout << "max = " << max << endl;
}

int main() {
  int hist[] = {3, 5, 4, 7, 6, 5, 2}; // answer: 20
  doHist(hist, sizeof(hist) / sizeof(int));
  return 0;
}

[5/28/2010]
The above implementation contains a bug. The following is updated version on 5/9/2010.

#include <iostream>
#include <sstream>
#include <stack>
using namespace std;

int DEBUG = 0;

//
// Note that if s->size() becomes 0, then left = start.
// This is useful when entry in hist[] can be zero.
// If all entries in hist[] are positive, then no need to use start,
// In that case, use -1 in place of start in this function.
//
void getMax(int hist[], stack<int> * s, 
            int newHeight, int right, int & max, int & start) {
  int height, left = 0, area;
  while (s->size() > 0 && hist[s->top()] > newHeight) {
    height = hist[s->top()];
    s->pop();
    left = (s->size() > 0) ? s->top() : start; 
    while (s->size() > 0 && hist[s->top()] == height) {
      s->pop();
      left = (s->size() > 0) ? s->top() : start; 
    }

    area = height * (right - left);
    if (DEBUG) printf("area: %d * (%d - %d) = %d\n", height, right, left, area);
    if (area > max) max = area;
  }
}

//
// Note that when hist[i] == top_v, we push i.
// In the acm judge site, it says skip i if equal. 
// But I feel somehow it can't keep track of the left value
// when multiple columns have the same height.
//
int doHist(int hist[], int len) {
  stack<int> * s = new stack<int>;
  int i, max, top_v;
  int start = -1; // the position before the last 0, used by left.

  max = 0;
  for (i = 0; i < len; i ++) {
    if (s->size() == 0) {
      s->push(i);
      continue;
    }

    top_v = hist[s->top()];
    if (hist[i] >= top_v) {
      s->push(i);
    } else if (hist[i] < top_v) {
      getMax(hist, s, hist[i], i - 1, max, start);
      s->push(i); 
      if (hist[i] == 0) start = i - 1;
    }
  }

  getMax(hist, s, 0, i - 1 , max, start);

  cout << "max = " << max << endl;
  return max;
}

int main() {
  int hist[] = {3, 5, 4, 7, 6, 5, 2}; // answer: 20
  doHist(hist, sizeof(hist) / sizeof(int));
  return 0;
}

[1/22/2013]

Found simpler and working solutions:

// Use stack. O(n). 

    int getArea(vector &h) {
        if (h.size() == 0) return 0;
        h.push_back(0);
        
        stack s;
        int i = 0, area = 0;
        
        while (i < h.size()) {
            if (s.empty() || h[s.top()] <= h[i]) {
                s.push(i ++); // if bar goes higher, push to stack.
            }
            else { // bar lower, pop and update area.
                int t = s.top();
                s.pop();
                area = max(area, h[t] * (s.empty() ? i : i - s.top() - 1));
            }
        }
        
        return area;
    }

// Binary search. O(n*log(n)). Call with getArea(height, 0, height.size() - 1).

    int getArea(int h[], int L, int R)
    {
        if (L > R) return 0;
    
        int minIndex = L;
        for (int i = L+1; i <= R; ++ i) {
            if (h[minIndex] > h[i]) minIndex = i;
        }
       
        int width = R - L + 1;
        int areaT = width * h[minIndex];
        int areaL = getArea(h, L, minIndex - 1);
        int areaR = getArea(h, minIndex + 1, R);
    
        return max(areaT, max(areaL, areaR));
    }