CareerCup

Could you expand on your assertion a little bit?

O(n^2) when the range of X-axis is divided into n segments.

O(nlogn), sort, then divide-conquer: choose highest bar, find max among: result from left region, result from right region, and the area of rectangle above the bar;

one of the ideas is to use DP.
but sorting will mangle the shape of the histogram, and you won't get the correct answer.

Why does sorting mangle the shape? Actually if you sort based on the height of each bar in the histogram, the answer would be max(L1 x n, L2 x (n-1), .... Ln x 1) x b where L1, L2, ... Ln is the ascending order of heights, b is the width of each bar and n is the total number of bars. The complexity would be O(n log n) due to sorting. How can it be done in O(n)?

Even a rectangle with very small height but large width can give us the right ans, so we have to take it into consideration

This wud require O(n) -
keep 2 points start and end
and a max area

Scan each point
if y of a point is diff from last point
This implies last rectangle has ended
calculate the area of last rectangle
compare it with max , if > than max , then change max
and repeat

O(N), no need to sort. no need to use stack/queue/tree..., O(N) array is enough for me. I think I have a perfect solution.

maxarea=a[0]*w;
arrh=new node [100]; // sorted array of nodes

struct node{
int h, starti,endi;
}
For i=0-n->length of histogram
{
1. remove all elements from arrh which have more height than a[i]
2. and while deleting check against maxarea and update maxarea accordingly
3. before u remove all these elements greater than a[i], check status of a[i], get starti for a[i], check if a[i] is already in arrh or not , if not then insert a[i] in the end after removing all elder elements along with calculated starti. If there were no elements greater than a[i] in arrh then starti=i;
4. now u have arrh of all elements having height less than or equal to a[i]. update this arrh by increasing endi for ell these elements
}

Now remove all elements left in arrh and update maxarea accordingly.
Now u have result in maxarea

The question asks maximal area. So my guess is that not just one rectangle but a rectangle consisting of consecutive rectangles with similar height should be found. In this case also we can do that in linear scan in O(n). Because we start with first one and keep going until we can no longer find a maximal area rectangle. Say the last in the sequence is rectangle 5. Then we start with five and do linear scan. In this way O(n) time we can find the maximal rectangle. Even if it were a single rectangle isn't it kind of like finding the maximum number among a set of numbers? Which can be done in O(n).

why people go to such length as DP and stack....
in histogram, each section as same width, so all we need to do is watch the height. set first height as max. if it's same height repeated, add it to original and assign it max. if it's not same and more than max then reset max to current value. just be careful to add same value repeating as u go and add it up.
it's simple and O(n)!

Linear search using a stack of incomplete subproblems
We process the elements in left-to-right order and maintain a stack of information about started but yet unfinished subhistograms. Whenever a new element arrives it is subjected to the following rules. If the stack is empty we open a new subproblem by pushing the element onto the stack. Otherwise we compare it to the element on top of the stack. If the new one is greater we again push it. If the new one is equal we skip it. In all these cases, we continue with the next new element.
If the new one is less, we finish the topmost subproblem by updating the maximum area w.r.t. the element at the top of the stack. Then, we discard the element at the top, and repeat the procedure keeping the current new element. This way, all subproblems are finished until the stack becomes empty, or its top element is less than or equal to the new element, leading to the actions described above. If all elements have been processed, and the stack is not yet empty, we finish the remaining subproblems by updating the maximum area w.r.t. to the elements at the top.
For the update w.r.t. an element, we find the largest rectangle that includes that element. Observe that an update of the maximum area is carried out for all elements except for those skipped. If an element is skipped, however, it has the same largest rectangle as the element on top of the stack at that time that will be updated later.
The height of the largest rectangle is, of course, the value of the element. At the time of the update, we know how far the largest rectangle extends to the right of the element, because then, for the first time, a new element with smaller height arrived. The information, how far the largest rectangle extends to the left of the element, is available if we store it on the stack, too.
We therefore revise the procedure described above. If a new element is pushed immediately, either because the stack is empty or it is greater than the top element of the stack, the largest rectangle containing it extends to the left no farther than the current element. If it is pushed after several elements have been popped off the stack, because it is less than these elements, the largest rectangle containing it extends to the left as far as that of the most recently popped element.
Every element is pushed and popped at most once and in every step of the procedure at least one element is pushed or popped. Since the amount of work for the decisions and the update is constant, the complexity of the algorithm is O(n) by amortized analysis.

@ theKK :
Keep It Short Simple

#ifndef MAX_RECTANGLE_IN_HISTOGRAM_H
#define MAX_RECTANGLE_IN_HISTOGRAM_H

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

class Histogram
{
public:
int get_max_rectangle(int histo[], int length, int & begin, int & end)
{
begin = end = 0;
int max_rec = histo[0];

stack<Info> min_stack;
for (int i = 0; i < length; i++)
{
if (min_stack.empty())
{
min_stack.push(Info(i, histo[i]));
}
else
{
Info & info = min_stack.top();
if (histo[i] > info.height)
{
min_stack.push(Info(i, histo[i]));
}
else if (histo[i] < info.height)
{
int new_begin = i;
while (histo[i] < info.height)
{
int size = info.height * (i - info.index);
if (size > max_rec)
{
begin = info.index;
end = i - 1;
max_rec = size;
}

new_begin = info.index;
min_stack.pop();

if (min_stack.empty())
{
break;
}

info = min_stack.top();
}
min_stack.push(Info(new_begin, histo[i]));
}
}
}

while(!min_stack.empty())
{
Info & info = min_stack.top();
int size = info.height * (length - info.index);
if (size > max_rec)
{
begin = info.index;
end = length - 1;
max_rec = size;
}
min_stack.pop();
}

return max_rec;
}

private:
struct Info
{
int index;
int height;

Info(int index, int height)
{
this->index = index;
this->height = height;
}
};
};

void test_max_rectangle_in_histogram()
{
int histo[] = {5, 3, 6, 8, 2, 1, 1, 1, 3, 8, 7, 6, 9 };
int length = sizeof(histo) / sizeof(*histo);
Histogram h;
int begin = -1;
int end = -1;
int max_rec = h.get_max_rectangle(histo, length, begin, end);
cout << "(" << begin << ", " << end << ") - " << max_rec << endl;
}

#endif // MAX_RECTANGLE_IN_HISTOGRAM_H

The plain old way .. O(n) .. what is the problem here ?

max = 0,
for all rectangles
{
area = l[i] x b[i]
if area > max
{
empty the answer set,
add the rectangle to answer set,
}
if area == max
{
add entry to answer set
}
}

//call it with start index and end index,
//for array[3] = {10,20,15} - call it as maxRect(array,0,2);

unsigned int maxRect(unsigned int *array, unsigned int start, unsigned int end)
{
    if ( end <= start )
        return array[start];

    unsigned int len = end - start + 1;
    unsigned int maxArea = 0;
    unsigned int minHeight = array[start];
    unsigned int minHeightPos = start;

    for(unsigned int i = start; i <= end; i++)
    {
        if ( array[i] < minHeight ) {
            minHeight = array[i];
            minHeightPos = i;
        }

        if ( array[i] > maxArea )
            maxArea = array[i];

    }

    unsigned int maxAreaLeft = 0;
    unsigned int maxAreaRight = 0;
    unsigned int maxRegion = 0;
    unsigned int finalMax = 0;

    if ( minHeightPos != end ) {
        maxAreaLeft = maxRect(array,start,minHeightPos);
        maxAreaRight = maxRect(array,minHeightPos+1,end);
        maxRegion = maxAreaLeft> maxAreaRight? maxAreaLeft:maxAreaRight;
        finalMax = maxRegion > (minHeight*len)? maxRegion: minHeight*len;
    } else {
        maxAreaLeft = maxRect(array,start,minHeightPos-1);
        finalMax = minHeight*len>maxAreaLeft?minHeight*len:maxAreaLeft;
    }

    cout << "start="<<start<<" end="<<end<<" maxAreaLeft="<<maxAreaLeft<<" maxAreaRight="<<maxAreaRight<<" minHeight="<<minHeight<<" len="<<len<<endl;

    for (int j = start; j <= end; j++)
        cout << array[j] << " ";

    cout << endl;

    return finalMax;
}

a good explanation with figures tech-queries.blogspot . com /2011/03/ maximum-area-rectangle-in-histogram.html

Class Histogram implements Comparer
{int lx;
int rx;
int y;
public compareTo(HistoGram that) // sort by x coordinates.
return this.rx.compareTo(that.rx) ;
}
static main void (string[] args){
//read from input file
// create array of HistoGram from inputs.
//First histogram to be sorted by x cordinates, so that we are not changing the real way they would be plotted in 2-d coordinates.
Histogram[] his = initialize(); //you can fill from file.
Array.sort(his); //It will sort based on the comparer, or you can pass the comparer expilic.
float area = FindArea(0,hc.length-1,his,0);
}
FindArea(int lc,int hc,his,area)
{
if(lc>hc)return;
int lowY = FindLowestY(his,lc,hc);
float area = (his[hc].rx - his[lc].lx).his[lowY].y;
if(area > maxArea)maxArea = area;
findArea(lc,lowY-1);
findArea(lowY+1,hc);
return area;
}
FindLowestY(Histogram[] his, int lc, int hc)
{
o(hc-lc) complexity to get lowest y having histogram
}

public int getMaxRectArea(int[] h) {
	int length = h.length;
	int[] l = new int[length];
	int[] r = new int[length];
	Stack<Element> stack = new Stack<Element>();
	for (int i = 0; i < length; ++i) {
		int curHeight = h[i];
		int count = 1;
		while(!stack.isEmpty() && stack.peek().height >= curHeight) {
			count += stack.pop().count;
		}
		stack.push(new Element(curHeight, count));
		l[i] = count-1;
	}
	stack = new Stack<Element>();
	for (int i = length-1; i >= 0; --i) {
		int curHeight = h[i];
		int count = 1;
		while(!stack.isEmpty() && stack.peek().height >= curHeight) {
			count += stack.pop().count;
		}
		stack.push(curHeight, count);
		r[i] = count-1;
	}
	int maxArea = 0;
	for (int i = 0; i < length; ++i) {
		int temp = (r[i]+l[i]+1)*h[i];
		if (maxArea < temp)
			maxArea = temp;
	}

	return maxArea;
}

O(n^2)

int maxArea(int[] arr)
	{
		int max = Integer.MIN_VALUE;
		
		for (int i = 0; i < arr.length; i++) {
			int height = continuousHeight(arr, i);
			if (height > max) {
				max = height;
			}
		}
		
		return max;
	}

	// Search on both sides of i, until a height smaller than it is found, break at that point
	int continuousHeight(int[] arr, int i)
	{
		int high = arr.length - 1;
		int low = 0;
		int count = 1;           // 1 for itself
		int cur = arr[i];         

		for (int j = i+1; j <= high; j++) {
			if (arr[j] < cur) {
				break;
			}
			count++;     // If continuous bigger add count
		}

		// Do same on other side
		for (int j = i-1; j >= 0; j--) {
			if (arr[j] < cur) {
				break;
			}
			count++;
		}

		return count * cur;
	}

and the complexity is O(n). Another idea is to use stack, also O(N).

http://charlesjob.blogspot.com/2007/06/largest-rectangle-in-histogram.html