A shot at an O(nlgn) algorithm.
Do a sweep line from top to bottom. Only look at the events when a new bar
is introduced (this is accomplished by sorting the bars based on height).
When a new bar arises, if there exist values immediately to the left and
right of the bar just merge them into a new
This problem was recently posted in a TopCoder match:
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm337
Checkout BuildingAdvertise problem in above editorial.
On 3/12/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
>
> I give a try to start at an O(mn) algorithm (where m i
I give a try to start at an O(mn) algorithm (where m is the size of the
longest bar)
Let Maxrect[i][j] denote the width of the maximum rectangle ending at the
ith position of height j
if(height[i] >= j)
Maxrect[i][j] = Maxrect[i-1][j]+1
else
Maxrect[i][j] = 0
We can traverse this array to find
I give a try to start at an O(mn) algorithm (where m is the size of the
longest bar)
Maxrect[height][width] =
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email
I think it should be O(n) which is an obvious lower bound since we need to
look at each rectangle at least once.
On 3/12/07, Balachander <[EMAIL PROTECTED]> wrote:
>
>
>
> 1. How to find the largest bound rectangle in a bar graph
>
> It seems a Google question was to solve this in O(Log n)
>
> Try
