Since I couldn’t solve the problem myself, I read up the concept and codes and managed to get it submitted via a Divide and Conquer (divide from middle) approach and a stack based O(n) solution. I also came up with a segment tree solution but it seems to be giving me a wrong answer. I’ve referred to different segment tree solutions but can’t seem to fix mine. Can anyone check out my approach and tell me what’s wrong here? (It gives me correct answer on the test cases provided)
Thanks!
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
and
http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/
will be handy!!
I’ve already tried reading those and I still couldn’t get my segment tree solution accepted.
I have got the code submitted via two different methods including the stack based approach you just gave link to, I just need to submit it via a segment tree once. I can’t figure out my mistake.
@epsilonalpha: You are getting WA because your approach is not right. Though you are finding out minimum number in the range using your query function, but you are not considering that number. I mean that you are using divide and conquer directly by dividing the array from the middle. Instead of this, you need to select the index of the minimum number that you are finding as middle index and then divide the array from that index.
I am giving you a example that why your approach is not right.
Consider the following array of heights and visit below link to see a photo describing how your query function is working.
Array: [2 3 3 1]
Link: Histogram
According to your solution, the array range [0,2] will never be considered which is indeed the correct answer. In a photo, The blocks in the merging are showing the answer in that range.
Visit this link given by @akshaym_96 for the correct solution using divide and conquer.
Thanks, the example helped and now I got it submitted!
The problem has been solved. Here’s the AC solution using Segment Trees for anyone needing this in future.