Author |
Topic: Biggest rectangle under histogram - Google intrvw (Read 7807 times) |
|
Ony
Newbie
Wow !!! U can see me !!!
Gender: 
Posts: 3
|
 |
Biggest rectangle under histogram - Google intrvw
« on: Jul 26th, 2008, 12:09am » |
 Quote  Modify
|
Sorry if these has been discussed before, could not find it, a link would be really helpful 
1)
Find the maximum rectangle ( area-wise ) completely contained inside the histogram.
The heights of the bars of the histograms are given in an array e.g. {4,2,10,8,12,13,15,8,6} and they have a fixed width w = 1, say.
The rectangles formed here are:
4X1, 2X9, 10X1, 8X6, 12X3, 13X2, 15X1, 8X6, 6X7
Thus, max-area rectangle = 8X6 = 48
2) Find the maximum area rectangle which has its 4 vertices inside the histogram, it may not be completely inside. e.g. 4X9 (from points 4 to 6), or 10X5 (from 10 to 15).
Need O(n*log(n)) soln atleast, preferably O(n).
O(n^2) is obvious compare a height with all to its left and right till you find one less than it for (1),
Compare a bar to the extreme end ones and keep on bringing the pointers closer to the bar, till the max for that bar is found.
Need urgently  , Help please
|
|
 IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #1 on: Jul 30th, 2008, 8:46am » |
Quote Modify
|
{4,2,10,8,12,13,15,8,6 }
Height of Rectangles of breadth 1 = Max ={4,2,10,8,12,13,15,8,6 }
Max-Height-1 = 15
Height of Rectangles of breadth 2 = { Max{4,2} Max{2,10}, Max{10,8}, Max{8,12}....{8,6}
Height-Max-2 = 13
Get all the Height-Max-i[]'s
Max of this array is the answer ( areas = answer * i )
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
chuncl
Junior Member
Gender:
Posts: 87
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #2 on: Jul 30th, 2008, 10:45pm » |
Quote Modify
|
1) this is for question one
keep left and right frontiers using dp, here is the code, comments are welcomed, actually i really hope to get any suggestions one this algorithm or coding part.
especially on the time complexity
thanks a lot
Code:float domaxAreaHist(int *h, int *left, int *right, const int n, int &l, int &r)
{
int i,j; float maxarea, areacur;
// left[i] and right[i] record first left/right frontier that is shorter thand h[i];
for (i=1; i<n; i++){
j=i-1;
while(j>=0){
// using dp
if(h[i]>h[j]) break;
else j=left[j];
}
left[i]=j;
}
for (i=n-2;i>=0; i--){
j=i+1;
while (j<=n-1){
if(h[i] > h[j]) break;
else j=right[j];
}
right[i]=j;
}
maxarea=h[0]; l=-1; r=1;
for (i=2; i<n; i++){
areacur=(right[i]-left[i]-1)*h[i];
if(areacur>maxarea){
maxarea=areacur;
l=left[i]; r=right[i];
}
}
return maxarea;
}
float maxAreaHist(int *height, const int n, int &l, int &r)
{
float maxArea;
int *left=new int[n];
int *right=new int[n];
left[0]=-1; right[n-1]=n;
int lshort, rshort;
maxArea=domaxAreaHist(height, left, right, n, lshort, rshort);
l=lshort+1; r=rshort-1;
delete[] left;
delete[] right;
return maxArea;
} |
|
|
| « Last Edit: Jul 30th, 2008, 10:50pm by chuncl » |
IP Logged |
It is fun
|
|
|
chuncl
Junior Member
Gender:
Posts: 87
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #3 on: Jul 30th, 2008, 10:48pm » |
Quote Modify
|
2) this is for question 2, pls don' t hesitate to criticize,
anyone can give time complexity of this? i think it should be something like O(nlogn), but need confirmation. thanks
Code:float maxAreaHist2(int *h, int n, int &l, int &r)
{
int i, maxh=-1, maxarea=-1, areacur;
// use multimap to hold current high histograms
// can use sorted array or link list , then every time do binary search. O(logn)
typedef multimap<int, int, less<int>, allocator<int> > High;
High M;
High::iterator lower,p;
for (i=0; i<n; i++)
M.insert(High::value_type(h[i],i));
for (i=0; i<n/2; i++){
// skip next short histograms
if(h[i]<maxh) continue;
else maxh=h[i];
// check on previous hold high histograms
// only keep the ones which is higher than current one
// map size is keeping decreasing
lower=M.lower_bound(h[i]);
//cout <<"lower is:"<< lower->first << '\t' << lower->second << endl;
M.erase(M.begin(), lower);
// check the area only with the historgram bars in the "high" map
for (p=M.begin();p != M.end(); p++){
areacur=min(p->first,h[i])*(p->second-i+1);
if (areacur>maxarea){
maxarea=areacur;
l=i; r=p->second;
}
}
}
return maxarea;
} |
|
|
| « Last Edit: Jul 30th, 2008, 10:52pm by chuncl » |
IP Logged |
It is fun
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #4 on: Jul 31st, 2008, 3:12am » |
Quote Modify
|
Can you please explain more about question that how it will have rectangle like 4X1, 10X1 and 15X1 ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
on Jul 31st, 2008, 3:12am, nks wrote:Can you please explain more about question that how it will have rectangle like 4X1, 10X1 and 15X1 ?
|
|
Each bar in the histogram has a width of 1. See attachment for all rectangles.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7528
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #6 on: Aug 3rd, 2008, 2:00pm » |
Quote Modify
|
Here an O(n) solution.
public class MaxAreaUnderHistogram
{
public int maxArea(int[] histo)
{
int maxArea = 0;
int left = 0;
int height = 0;
int[] stack = new int[2*histo.length+2];
int sp = -1;
for( int i=0 ; i<=histo.length ; i++ ){
int val = i<histo.length ? histo[i] : 0;
if( val<0 ) val=0;
if( val>height ){
stack[++sp] = left;
stack[++sp] = height;
left = i;
height = val;
} else {
int right = i;
while( val<height ){
int area = height*(right-left);
System.out.println("test [" + left + ".." + right + "]x[0.." + height + "]" + " area " + area);
if( area>maxArea ){
. maxArea = area;
}
if( stack[sp]<=val ){
. height = val;
} else {
. height = stack[sp--];
. left = stack[sp--];
}
}
height = val;
}
}
System.out.println("best area: " + maxArea);
return maxArea;
}
public static void main(String[] args)
{
int[] histo = new int[] {4,2,10,8,12,13,15,8,6};
new MaxAreaUnderHistogram().maxArea(histo);
}
}
|
| « Last Edit: Aug 4th, 2008, 7:56am by Grimbal » |
IP Logged |
|
|
|
chuncl
Junior Member
Gender:
Posts: 87
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #7 on: Aug 4th, 2008, 8:05am » |
Quote Modify
|
Grimbal, this is for question 1) right? could you elaborate why it is o(n)? it seems like o(n2), thanks
|
|
IP Logged |
It is fun
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7528
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #8 on: Aug 12th, 2008, 3:02pm » |
Quote Modify
|
The outer for loop is O(n) obviously. Inside the for loop is a push that gets executed max n times (n times 2 items).
The while inside the for either sets height=val which terminates the loop, or pops a value from the stack. Both of these actions can happen only n times overall.
So the inner while loop is never executed more than 2n times.
|
|
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #9 on: Sep 21st, 2009, 5:45pm » |
Quote Modify
|
How can we do the question 2) in time less than O(n**2)
|
|
IP Logged |
|
|
|
allbatros
Newbie
Posts: 50
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #10 on: Oct 18th, 2009, 6:18am » |
Quote Modify
|
on Sep 21st, 2009, 5:45pm, mistaken_id wrote:| How can we do the question 2) in time less than O(n**2) |
|
the same grimbals solution can be applied to this case.
keep on building a increasing and decreasing sequence and keep on calculating the current max rect area. as soon as you get a sequence which again starts increasing pop out elements to convert it to increasing-decreasing sequence.
something like you are maintaining a convex hull
|
|
IP Logged |
|
|
|
R_P
Newbie
Posts: 6
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #11 on: Mar 13th, 2010, 2:05pm » |
Quote Modify
|
on Aug 3rd, 2008, 2:00pm, Grimbal wrote:
Could someone give a high level description of what the code posted by Grimbal does. I am finding it hard to understand the logic from the code.
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #12 on: Mar 15th, 2010, 3:26am » |
Quote Modify
|
Though Grimbal has posted an order n solution. Here is a O(n.log(n)) solution for 1.
Code:static int area = 0;
void maxArea(int[] a, int beg, int end)
{
if (beg >= end)
return;
int minIndex = minIndex(a, beg, end);
if (area < (end - beg + 1) * a[minIndex])
area = (end - beg + 1) * a[minIndex];
maxArea(a, beg, minIndex - 1);
maxArea(a, minIndex + 1, end);
}
public static int minIndex(int[] a, int beg, int end)
{
int minIndex = beg;
for (int i = beg; i < end; i++)
if (a[i] < a[minIndex])
minIndex = i;
return minIndex;
} |
|
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #13 on: Mar 17th, 2010, 11:42am » |
Quote Modify
|
allbatros, seems question 2 can't be done less than 0(n2). In the first question its just suffice to maintain increasing sequence but here we have to maintain decreasing sequence also. This will take 0(n2) time.
Grimbal, any commnet on this ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #14 on: Mar 17th, 2010, 1:01pm » |
Quote Modify
|
For two, I think you can just start at both ends. And if one end is greater than the other, move the other end till you find a greater element.
So with
{4,2,10,8,12,13,15,8,6}
we have a[0]=4, a[8]=6, giving a current rectangle of size 4*9=36
Then we increase the lower bound, because it's least. a[0]->a[1]->a[2]
a[2]=10, a[8]=6 this gives 7*6=42
So now we decrease the upper index; a[8]->a[7]->a[6]
a[2]=10, a[6]=15 ==> 5*10=50
a[4]=12, a[6]=15 ==> 3*12=36
a[5]=13, a[6]=15 ==> 2*12=24
So our maximum rectangle had size 50.
|
| « Last Edit: Mar 17th, 2010, 1:04pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R_P
Newbie
Posts: 6
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #15 on: Mar 18th, 2010, 3:35am » |
Quote Modify
|
on Mar 15th, 2010, 3:26am, abhay.bansal wrote:Though Grimbal has posted an order n solution. Here is a O(n.log(n)) solution for 1.
Code:static int area = 0;
void maxArea(int[] a, int beg, int end)
{
if (beg >= end)
return;
int minIndex = minIndex(a, beg, end);
if (area < (end - beg + 1) * a[minIndex])
area = (end - beg + 1) * a[minIndex];
maxArea(a, beg, minIndex - 1);
maxArea(a, minIndex + 1, end);
}
public static int minIndex(int[] a, int beg, int end)
{
int minIndex = beg;
for (int i = beg; i < end; i++)
if (a[i] < a[minIndex])
minIndex = i;
return minIndex;
} |
|
|
|
I doubt if this is O(nlogn). Incase the minindex always occurs at first index of each of the subarrays, the recurrence relation would be like T(n) = T(n-1) +O(n) which would be a O(n^2) soln. Correct me if i'm wrong..
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #16 on: Mar 18th, 2010, 6:41am » |
Quote Modify
|
Worst will be O(n^2) but the average case is O(n.log(n)).
|
|
IP Logged |
|
|
|
swarnaprakash
Newbie
Gender:
Posts: 4
|
|
Re: Biggest rectangle under histogram - Google int
« Reply #17 on: Mar 22nd, 2010, 10:00am » |
Quote Modify
|
1) is same as "Largest rectangle in a Histogram" asked in Ulm local contest 2003. You can find analysis here. 6 Solutions are given.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print