Next Greater Element I - Leetcode 496 - Python

0:00 - Read the problem
2:34 - O(n * m) Explained
5:50 - O(n * m) Coded
7:23 - O(n + m) Explained
12:34 - O(n + m) Coded

leetcode 496

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

[vdyb]

You are the best explainer for leetcode problems bar none on the internet !!!! Wow .... !!! Thank you.

[laughingdog]

That was one of the best explanations I've seen for this problem, with clean, comprehensible code! ...and today I learned "enumerate". If nothing else, leetcode has been teaching me how to write MUCH cleaner python code thanks to channels like these. Thank you!

[smartsoothing]

This is definitely not an easy problem!!

[paul_tee]

i don't really see why the monotonic solution is O(n) time, where n = len(nums2). suppose nums1 =[1, 2, ..., n] and nums2 = [n, n-1, n-2, ..., 1]. in this case, don't you need to perform 1+2+...+n checks, which is on the order of n^2?

EDIT: ok i got it, you don't need to perform 1+2+...+n checks, because of the decreasing nature of the stack. instead, you perform 1+1+...+1 checks because if you can't pop the first guy out, you surely can't pop any other the guys before it out. neat idea using monotonicity!

[foofoo]

I could'nt get my head around a monotonic stack after reading a few explanations off LC but you have made it very easy for me to understand the concept. Thank you!

[lingxu]

Always enjoyable to watch your video solutions, thanks!

[manjultripathi]

Any better way to explain a LC problem than above can't be thought of, ever.Period!

[transgenicznyogorek]

Good explanation! My only nitpick is at 10:24 that the stack is monotonically *increasing, not decreasing* - the rightmost element is considered the top of the stack, and every following element is going to be greater than the top of the stack. That confused me for a while since R to L solution uses a decreasing stack :P

[Arnaud-br]

Great presentation! I've done it almost exactly the same even before seeing the code, that's how clear it was! I'm puzzled by the exec time on Leetcode though. My first solution using a kind of 'enhanced' brute force also ran in 0ms 🤔

[gauravmasand]

I was stuck in understanding of problem what to do nice and simple easy to get explanation of question i got solution in mind at 2:30 Very nice

[chankwongyin]

hey Neetcode, could you summarize all the questions you have done and make a leetcode list link to us? thx!

[jasonl.]

tbh this should be a medium question (without knowing the pattern), at least for the optimum solution.

[polasumanth]

Congratulations for 100k subscribers🎉🥳👏👏👏

[shalinisangal]

Great explanation, with ur explanation feeling like it was so easy. Thank u so much

[ThrowAway-pc]

You really don't need the hash map for the n^2 solution. Just keep track of the indexes as you loop using enumerate.

[cc-tojn]

def not an easy lol, great job as always

[tamarehrenreich]

Perfect explanation. Very helpful. Thanks so much.

[dp]

for 9:39, wouldn't [2, 0, 1, 3, 4] be an example of an array for which the next greater assumption wouldn't hold true?
3 is the next greater element for 2, but it's not the next greater element for 0, even though 0 would be on the stack (1 is the next greatest for 0).

[ninjacloud]

Thank you so much for all the Amazing videos you have made so far. Could you please add videos for some of HARD questions for Google, for example "Guess Word" and other such Leetcode questions. That would be a great help!!
Thank you once again!!!

[iliauk]

Awesome video!

Could we also have something like so (not sure if same complexity since seems shorter)

res = {}
stack = []
for v in nums2:
while stack and stack[-1]<v:
old_val = stack.pop()
res[old_val] = v
stack.append(v)

return [res[v] if v in res else -1 for v in nums1]