**Question:**Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.

(Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.)

**Answer:**A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time but this will be huge if we have a big histogram with thousands of bars. So we need to have an algorithm of O(n*logn) or O(n).

Lets see if we can find one such solution:

There are a few invariants, we can use for this problem:

- If we include bar i, maximum possible height of rectangle including that bar will be h(i), height of that bar.
- If we include bar i, maximum possible width of rectangle including that bar will be L+R+1, where:

- L is number of adjacent bars to the left of ith bar and height greater than or equal to h(i).
- R is number of adjacent bars to the right of ith bar and height greater than or equal to h(i).

For the figure in question, if we include bar i, we will have max area as given in below pictures.

Now our task remains as follows:

1) Get Li2) Get Ri3) Get area of rectangle for bar i: A(i) = h(i) * (Li+Ri+1)4) Find max value of A(i)

**How to get Li:**

Li is the number of adjacent bars to the left of ith bar and height greater than h(i). How can we calculate this?

One solution is to for each I, traverse through i to 0 until you get a bar of height less than h(i). This will be an O(n^2) solution to find all the Li.

But we can have a better solution, which works in less than O(n^2). Lets see an example; in example figure, what is the farthest bar greater than or equal to h(9) (h(9) =2 in our case). Here we are seeing that 4th bar is just short of h(9), so we can move left till 5th bar. So we don’t need to compare with 3rd, 2nd and 1st bar in this case.

Similarly, if I want to put a new value in the stack, which points we should compare h(i) to find L? : 10th, 9th and 4 th. Coz if we can include 9th bar, we can certainly include 8th, 7th, 6th and 5th bar as they have height greater than h(9).

Now if I use a stack and put only those bars in stack, which are possible candidates. And pop those values until I get a bar with height less than h(i). Finally Li = (i – TOP-of-stack).

**Complexity:**In first impression, this solution seems to be having O(n^2) complexity. But if we look carefully, we can just put at the max N bars in stack at any point in time. And we are not pushing any bar twice. So we can pop at most N bar while calculating Li for complete histogram. So work time complexity is O(n+n) = O(2n) = O(n)

**How to get Ri:**

Similarly as we found Li. Just start from the end in place of beginning.

**Code:**

int largestArea(int arr[], int len)

{

int area[len]; //initialize it to 0

int n, i, t;

stack<int> St; //include stack for using this #include<stack>

bool done;

for (i=0; i<len; i++)

{

while (!St.empty())

{

if(arr[i] <= arr[St.top()])

{

St.pop();

}

else

break;

}

if(St.empty())

t = -1;

else

t = St.top();

//Calculating Li

area[i] = i - t - 1;

St.push(i);

}

//clearing stack for finding Ri

while (!St.empty())

St.pop();

for (i=len-1; i>=0; i--)

{

while (!St.empty())

{

if(arr[i] <= arr[St.top()])

{

St.pop();

}

else

break;

}

if(St.empty())

t = len;

else

t = St.top();

//calculating Ri, after this step area[i] = Li + Ri

area[i] += t - i -1;

St.push(i);

}

int max = 0;

//Calculating Area[i] and find max Area

for (i=0; i<len; i++)

{

area[i] = arr[i] * (area[i] + 1);

if (area[i] > max)

max = area[i];

}

return max;

}

**Complexity:**4 steps:

1) Finding Li = O(n)

2) Finding Ri = O(n)

3) Calculating Ai = O(n)

4) Finding max A(i) = O(n)

So Final complexity is O(n) + O(n) + O(n) + O(n) = O(n)

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
SuryaDidn't get the question.

Akash@Surya: I mean the area of largest rectangle that fits entirely in the Histogram. Please refer figures above the code for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.

Thanks for your query, I have updated the post for more clarity.

ManishI think:

"L is number of adjacent bars to the left of ith bar and height

NOTless than h(i)"and

"Li is the number of adjacent bars to the left of ith bar and height

NOTless than h(i)"correct?

Akash@Manish: Yes, seems like a typo. Thanks for the correction.

ManishYou may want to review your post before others get confused:

"we can certainly include 8th, 7th, 6th and 5th bar as they have height (strike)less(/strike)

greaterthan h(9)."Akash@Manish: Thanks for the correction. I reviewed the post once and it seems that it's ok now. I wrote this one in a hurry :)

AnonymousI didn't understand where the stack first came into picture ? can you please elaborat ? Thanks.

Anonymousare you sure u have given solution for maximum area rectangle not continuous maximum area rectangle???

becoz ur solution is giving wrong output...

for ex arr={9,6,2,1,3,5,4,8,2,7}

its giving solution as 12 but solution should be around 25 or may be bigger

Akash@anonymous1:If you go through sectionHow to get Li, you will see the highlighted area where the advantage of using stack has been shown. From then onwards, we talked in term of stack.@anonymous2:yes, it'scontinuous maximum area rectangle. What do u mean byNon-continuous maximum area rectangle.How do u get 25 as answer for ur input?gaur_ashuIf possible for the input which you provided can you provide the values of

Arr[] for Li and Ri.

Aso where did you

for Ri: t-i-1 and for Li: i-t-1

DDAnonymousI really liked your solutions.....specially finding the complexity ..that is it is of O(N).

I solved it in the same way but still I was thinking its complexity in worst case would be O(n2), but with your description and thinking I found you are right...

Akash@Anonymous: Thanks!

Anonymouscould you please explain it better? I am finding it hard to understand your explanation.

To get Li do we start from left or right? why are you considering only h(9)? how do we select an element to push on to stack.. I am completely lost :( please help me

Akash@Anonymous: I will see if I am able to rewrite it. Between, you are welcome to ask any doubts at [akash dot agrawal dot 84 at gmail dot com]

AnonymousNice post. What if we also want to retrieve the position of the max rectangle? also the bool done isn't used.

AnonymousFollowing two are contradicting:

If we include bar i, maximum possible width of rectangle including that bar will be L+R+1, where:

L is number of adjacent bars to the left of ith bar and height greater than or equal to h(i).

R is number of adjacent bars to the right of ith bar and height greater than or equal to h(i).

How to get Li:

Li is the number of adjacent bars to the left of ith bar and height less than h(i). How can we calculate this?

One solution is to for each I, traverse through i to 0 until you get a bar of height less than h(i). This will be an O(n^2) solution to find all the Li.

In Li is number of bars left to (i)th bar with height GREATER than h(i)

but in you are saying

Li is the number of adjacent bars to the left of ith bar and height LESS than h(i)

isnt this contradicting? or am i missing something?

Akash@Anonymous1: You can get the location of start and end bar very easily. In last step we are calculating max area. In that step, we can easily save the bar_no, for which we have max area and then we can get start and end bar constituting that area.

Secondly, I used 'done' for some debugging purpose, we can left it out.

@Anonymous2: Yeah! That is a typo. I will correct that. It should be 'greater' at both the places. Thanks for pointing it!

Omar OthmanThanks Akash for the excellent blog. Just a small revision: Under the subtitle

How to get Li:, it should begreater than or equal tonotgreater than.AnonymousI couldn't have found as good an explanation of this problem anywhere on the internet. Thanks for the great blog!

RDRun your code for 4 bins as follows

1 1 4 4

you will get a wrong answer ..Answer should be 8 and you will get 16

Akash@RD: I am getting answer as 8 for 1,2,4,4

Are u sure to pass right value of len?

AnonymousHello,

In your figure displaying the maximum rectangle candidates, for h(9), you wrote "9 => 18", when it should be "9 => 12".

Volume of Sphere FormulaReally i like your solutions very much.The solutions you gave are very helpful in solving the problems i am facing from last few days.

Akash@Volume of Sphere Formula: thanks buddy...

What is a HistogramThe best part of histograms is that we can collect all knowledge of the facts and figures by its area.

AnonymousSimple Python SolutionNo Stack Useddef leftRange(arr):

lval= [0]*len(arr)

for i in range(1,len(arr)):

if(arr[i]<=arr[i-1]):

j=i-1

while True:

lval[i]+=lval[j]+1

j=j-1-lval[j]

if(j<0 or (arr[i] > arr[j])):

break

return lval

------------

def rightRange(arr):

rval= [0]*len(arr)

for i in range(len(arr)-2,0,-1):

if(arr[i]<=arr[i+1]):

j=i+1

while True:

rval[i]+=rval[j]+1

j=j+1+rval[j]

if(j>len(arr)-1 or (arr[i] > arr[j])):

break

return rval

------------

def best_hist_sol(arr):

lval = leftRange(arr)

rval = rightRange(arr)

area = [0]*len(arr)

for i in range(1,len(arr)):

area[i]=(lval[i]+rval[i]+1)*arr[i]

return max(area)

Vijay jainvery good post... clears all my doubts... thanks..

vsn harish rayasamExcellent explanation :)

Anonymouswe can calculate Li using DP.

Let left[i] represents length of adjacent neighbors that has higher height than A[i] to its left.

For i = 0, left[0] = 0,

For left[i] > left[i-1] (i > 0), left[i] = left[i-1] + 1 if A[i] <= A[i-1], or 0 if A[i] > A[i-1].

right[i] can be calculated the same way from the right.

then in a for loop, calculate area[i] = (left[i] + right[i] + 1) * height[i]

Global IasBest ias coaching in bangalore

.www.globalias.in

Miq ClassesBest ssc coaching in Bangalore

http://www.miqclasses.com/ssc-coaching-centers-in-bangalore/