SPOJ - HISTOGRA - Largest Rectangle in a Histogram help needed

general
, , , , , ,
1

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!

2

See this code. It’s and simple and no need of segment tree

3

Largest Rectangular Area in a Histogram using Stack - GeeksforGeeks
and
Largest Rectangular Area in a Histogram using Segment Tree - GeeksforGeeks
will be handy!!

1 Like
4

@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.

1 Like
5

The problem has been solved. Here’s the AC solution using Segment Trees for anyone needing this in future.

6

https://ideone.com/gRTOfr
why does my code gives Time limit exceed error all the time … i have used the stack approach to solve the problem.

7

I’ve already tried reading those and I still couldn’t get my segment tree solution accepted.

8

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.

9

Thanks, the example helped and now I got it submitted!

10

I see you’re using Java.

  1. Try using fast IO.
  2. I think that in the second loop, you should use
    long tempArea = temp * (stack.empty() ? n : n - 1 - stack.peek());
  3. Return the value from the function and print it in the main method, instead of printing it in the function itself. In practice, we design functions keeping encapsulation in mind. We give an input, and we expect an output. The values are generally returned instead of printed.
1 Like
11

Can someone please tell what is wrong with this code?

12

Please?

13

can someone please see what’s wrong with my code. i have tried everything possible

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int getMaxArea(ll hist[], ll n)
{
stack s;

ll max_area = 0;

ll tp;
ll area_with_top;
ll i = 0;
while (i < n)
{
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
else
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
}
while (s.empty() == false)
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);

    if (max_area < area_with_top)
        max_area = area_with_top;
}

return max_area;

}
int main()
{
for(;;){
ios::sync_with_stdio(false);
cin.tie(0);
ll n,i;
cin>>n;
if (n==0)
return 0;
ll h[n];
for(i=0;i<n;i++)
cin>>h[i];
cout <<getMaxArea(h, n)<<endl;

}

}