LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python

0:00 - Intuition
5:44 - Conceptual Algorithm
13:58 - Coding optimal solution

#Coding #Programming #CodingInterview

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[xingdi]

Even with the video, this problem is still hard for me to understand and solve. but, anyway, thanks for explaining

[mapo]

how do you come up with this in an interview. just knowing monotonic stack isn't enough, must be legit einstein's cousin

[abhilashpadmanabhan]

Dude's awesome as he always is! Just a suggestion, if we add a dummy [0] to the right of heights, the extra handling for right boundary can be avoided. I tried that and got accepted. :)

[tarunchabarwal]

I watched couple of videos, but this one does the job :)

[kunlintan]

Thanks! Your explaination helps a lot!

[xiaonanwang]

It's a pretty hard question. But NeetCode explained it in a pretty good way. At first, I couldn't understand it. But in the end, I found it a very good video.

[pl]

this is awesome. I don't know how someone can come up with the solution in an interview for the first time.

[bchen]

Bumped into one of your earliest uploads and I am amazed at your progress. You improvements in tone is impressive!

[fattysun]

I would've never come up with that good of a solution with my abilities right now. Leetcode has humbled me a lot since I am an almost straight A student in college. I trip up on mediums and hard easily, it shows that GPA doesn't mean anything and I still have a long way to go with my problem solving skills.

[mandy]

Repetition really helps nail down the point into my head till it clicks. Liked and subscribed. Thank you!

[justinUoL]

sincerely the best explanation for lc questions in 21st century. thank you!

[technophile_]

I think this is one of those problems that can be solved in an interview setting if, and only if you've solved it before. There's no way someone would be able to come up with this solution in an interview 😮‍💨

[chenhaibin]

The stack O(N) method deserves to be a hard problem. But you explained it so well, it did not feel that difficult after watching your video. thank you

[vishaljadhav]

Honestly, this is one of your weaker explanations - i don't know why you started using word "pop" right at the start. We really need get the core idea first and then think of the stack to solve it - stil great work on explanation of algorithm/code but wish it was better on the intuition.

[aymanehrouch]

is it even possible to come up with the solution to this problem if you've never seen it?

[gregoryvan]

you made it easy to understand but I dont think I could come up with that answer in an interview setting if I have never seen the problem before....

[JOP_Danninx]

This was my first ever hard problem, and I was so close to solving it-

I hadn't considered the fact that I could leave some stacks until the end to calculate them using [ h * (len(height)-i)], so I had that for loop nested inside the original one, which gave me some time limit issues.

These videos explain things super well, thanks 👍

[ammarqureshi]

man you are underrated, such a clear explanation. keep it up my guy!

[dera_ng]

Imagine if your Kryptonite was a leetcode question. Well, ladies and gentlemen, I present to you....

[niraiarasu]

I solved the problem by myself and cameup with this intutive approach, just find next smaller and prev smaller element

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
nse = [n]*n
pse = [-1]*n
ans = 0

#nse
stack = [0]
for i in range(1, n):
while stack and
index = stack.pop()
nse[index] = i
stack.append(i)


#pse
stack = [n-1]
for i in range(n-2, -1, -1):
while stack and

index = stack.pop()
print(index)
pse[index] = i
stack.append(i)

#cal each bar value find diff and multiply with bar value
for i in range(n):
a = nse[i] - i
b = i- pse[i]
unit_value = (a+b-1)*heights[i]
ans = max(unit_value, ans)

return ans