Histogram Area Problem Concept

#1

I didn’t get the histogram area problem. Can anyone kindly explain?

So, I know like,

push(): jab current bar ki value previous bar ki value se larger ho then push in the stack,
WHY!!

pop(): agar current bar ki value previous bar ki value se smaller hai then pop from the stack,
WHY!!

case 1: agar pop karne ke baad stack empty nai hai then

‘i’ is the variable signifies current bar index
width=(i-s.top()-1)
length=hist[s.top()]
area=length*width

case 2: agar pop karne ke baad stack empty hai then

‘i’ is the variable signifies current bar index
width=i
length=hist[s.top()]
area=length*width

PS. I watched Prateek Bhaiya’s video so don’t attach any video if you’re thinking like that.

#2

Hello @Kinjal,

Read the following article. IT has explained this approach:

  1. push(): jab current bar ki value previous bar ki value se larger ho then push in the stack,
    WHY!!
    Reason:
    the new bar can also contribute in the rectangle formed by the previous bar.

  2. pop(): agar current bar ki value previous bar ki value se smaller hai then pop from the stack,
    WHY!!
    Reason:
    The new bar would not contribute in the rectangle formed by the previous bar. Thus, we will keep popping the bars until the height of bar at stack top is not smaller or equal to the new bar.

Hope, this would help.

1 Like
#3

Thanks mate. Now I got the reasons behind push() and pop().

#4

Anytime @Kinjal,

Please, mark it as resolved.

#5

So what I have got from my deep understanding is that hum iss code meh har ek rectangle bar ke baje se jo area meh change ya contribution ho rha hai, woh har time check kr rhe hai aur maxarea meh save kr rhe hai.

#6

Hey @Kinjal,

yes, we are trying to do something similar.

#7

still I’m getting wrong answer.

#8

Hey @Kinjal,

You must have done a mistake.
Cross verify your code with:

Let me know if you still can’t find it.

#9

so I didn’t find it. I mean, we did it same way but mine one is messy.

#10

So, my silly mistake in data type. I should use long instead of int.

#11

Hey @Kinjal,

So, is it resolved now?

#12

yes, it is. I have raised another problem based on Stacks(Redundant Parenthesis) so can you able to answer that?

#13

Hey @Kinjal,

Someone else mist have acknowledged it.

#14

how can you be sure? I raised it for hours ago?

#15

Because @Kinjal, i cannot see your doubt on the portal which means someone else has marked it as acknowledged.

He would soon respond to it.

#16

really!! Are you sure, mate! Maybe you overlooked it. I’m just stuck on this problem.

#17

See @Kinjal,

image
image1920×1080 177 KB

#18

Thank you for your concern, mate. Good night.