Divide and conqure approach

#1

is this right approach using divide and conqure
and what is time complexity like O(nlogn + n) ?
code - https://ide.codingblocks.com/s/247858

#2

No there is no divide and conquer approach imo, instead there is an O(N) approach using stack.
For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively. We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’

Here is the code for this approach https://ide.codingblocks.com/s/247960
Finding the just greatest element towards left and towards right for any index using stack is a well known problem

#3

ide- https://ide.codingblocks.com/s/247869 i tried to code but it is not working could you please have look at my code and tell what’s wrong in it

#4

refer to the code here
ur code lacks the last while loop

also print the final answer once

1 Like
#5

i edit my code but giving wrong output.