Next Greater Element I - Leetcode 496 - Python

[@vdyb745]

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

[@smartsoothing776]

This is definitely not an easy problem!!

[@JustinK0]

it definitely it easy, i got the O(n^2) solution on the first try, even if the O(n) is a bit harder it doesnt really matter if an easy solution still exists.

[@chrischika7026]

@@JustinK0 they are obviously referring to the O(n) solution and it does matter because it is more efficient and that is what the interviewer would want.

[@berserker556]

Yeah it did not feel easy to me

[@thebigpart783]

@@JustinK0 if you show up with the n^2 solution they won't hire you so no it is not easy ...

[@cicakmuhamed]

@@JustinK0 Justin, solving a problem in suboptimal solution is easy for some of the hardest problems on leetcode. The whole point of leetcode is finding an optimal solution...

[@foofoo17]

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!

[@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!

[@taiwoadebisi9315]

How is this easy?!!

[@ajain2603]

Same question

[@manjultripathi8309]

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

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

[@lingxu9697]

Always enjoyable to watch your video solutions, thanks!

[@leventoz9530]

First calculate the next greater element (NGE) of each element in nums2 starting from the right, such that NGE(nums2.length-1) = -1 and NGE(i) = max(nums[i+1], NGE(i+1)). Store the values in a hashmap. This is O(nums2.length). Next, iterate over the elements of nums1 from left to right, accessing the values in the hashmap. This is O(num1.length).

[@realoctavian]

You can't calculate the next greater like that. Take for instance this input: 5 4 2 1 3 7. At some point the next greater is neither nums[i + 1], nor NGE(i + 1). Cool idea though, I was trying to find something similar.

[@chankwongyin7455]

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

[@lex-zt6uc]

That would be amazing

[@ingluissantana]

Such a great explanationnnnnnn thankssssss 🙏🏼🙏🏼🙏🏼🙏🏼

[@jasonl.7466]

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

[@shalinisangal84]

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

[@andreytamelo1183]

Thanks!

[@SnowdenFu-jh6bx]

question: why don't we directly loop num1?

[@dp2120]

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

[@dp2120]

ah nvm - I see, we compare each new value to the top of the stack to check if it's the next greater

[@tamarehrenreich7428]

Perfect explanation. Very helpful. Thanks so much.

[@polasumanth9826]

Congratulations for 100k subscribers🎉🥳👏👏👏

[@davyroger3773]

All you gotta do is make a sorted copy of nums2, then for every i in nums1, slice the ordered list at the ith position to get all of the possible values greater than i in nums 2. Then call a separate method that takes the sliced ordered list , the i value , and the og nums2, make another slice at pos i this time in the og nums2. def find_elem(self,ordered_slice, nums2, value): pos = nums2.index(value) unordered_slice = nums2[pos+1:] now we can do a quick list comp to keep all of the values in the unordered slice list if they are in the ordered slice possible = [i for i in unordered_slice if i in ordered_slice] At this point there will be two possible outcomes, 1 the list is empty indicating that we couldn't find any value greater than i to the right of i, 2 that we were able to find such a value(s), and have stored them in the order that we found them. So all thats left to do is if possible == [ ]: self.tracker.append(-1) else: self.tracker.append(possible[0])

[@akhilr94]

bro sorting is O(nlogn)

[@akhilr94]

still can't wrap my head around an algorithm like this, ie the O(n + m) one. obv I can understand the explanation. but how can it come naturally during interviews?

[@alfamatter12]

It won't 😢

[@memeproductions4182]

Why do you need an hashmap in brute force? wouldn't just iterate nums1 and for each iterate nums2 to find the corrispective number and then go on and find the successor still be O(n *m) but without extra memory?

[@akhilr94]

as you have mentioned, there are 2 find operations in nums2, leading to (n * m * m).

[@faithcyril513]

@@akhilr94 the iteration over nums2 is the finding process so it will be O(n*m) not O(n*m*m)

[@avinashtiwari4025]

How did you calculate the space complexity for the stack part?

[@cc-to2jn]

def not an easy lol, great job as always

[@NeetCode]

Agreed!

[@iliauk1]

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]

[@hasferrr]

i love you neetcode

[@ninjacloud4748]

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!!!

[@lingyuhu4623]

Why cannot I first append element in stack, then while loop? The order makes a big difference, but I dont know the reason

[@marlieemam216]

case if num2 array is 5, 4, 3, 2, 6 doesn't this make the second solution O(m * m ) where m is size of num2 ?

[@ibrahimmalik4155]

In the for loop, you don't need to check if cur is present in nums1. As the question states that nums1 is a subset of nums2. Just a little nuance that could help out your solution. Great job!

[@olawaleojodu6704]

Without the checks, I think it will throw a key error if you're trying to lookup an element not present in an num1 hashMap??

[@orangethemeow]

I brute forced it but somehow beat 97.62% of python 3 submissions For the second solution, do we need to check if cur is less than the top of the stack when adding it in?

[@alexmercerind]

lmao

[@sanooosai]

thank you sir

[@zhonglingsun6743]

Love all the videos on your channel. Could you possibly cover #31. Next Permutation which is similar to this one but a bit more complex?

[@niharikkatyagi4089]

The line ->while cur > stack[-1] is giving me the error: '>' not supported between instances of 'int' and 'list' I dont understand why, what do I do??

[@samagrasinghtomar79]

The stack push op needs to be done unconditionally. The O(m+n) solution won't work as it is in the video.

[@zergenzerg6853]

At first I was initially thinking you can probably solve this with a stack instead of a hashmap. You can just push the values onto the stack from the end and pop them off as they're greater? Let me finish the video

[@greatestever2914]

the easy are harder than some of the hards

[@kirillzlobin7135]

Great video

[@whathappened2872]

How old are you now?I'm learning js right now should I do this practice parallel in Python I have a knowledge of Python but not in dsa exactly

[@atifzia124]

n2 is fine, 😢 it ain't easy to lower complexity at easy level

[@Vishal_84_k]

2nd bro💓💓 lots of respect💥💥

[@ruchitagarde4642]

What would be the solution if nums2 = [5,1,6] nums1 = [5,1] This result=[6,6] or result = [-1,6] ?

[@sachidanandanradhakrishnan6630]

[6,6] r8?

[@droft1312]

Great video! Do you think you could cover #828 - Count Unique Characters?

[@JasonAhn-u5u]

@12:59 Can anyone please explain to me line 4, where it's written as { n: i for i, n in enumerate(nums1)}? Shouldn't it be {i:n for i, n in enumerate(nums1)} to match both i and n? Thanks!

[@sivaprakash_prabakaran]

we want the numbers as keys and their index as values, to quickly look up and find the index of the numbers; thats why we are doing n:i; { n: i for i, n in enumerate(nums1)} is a short hand for creating dictionaries on the go; like we have list comprehension, this is dictionary comprehension. enumerate will result in a list of [index, value] pairs; we match the index with i and numbers with n (i, n) and we use those i and n as key:value pairs of dictionary but in reverse; we use numbers n as keys and index i as values; so i:n

[@junkim4323]

I love your videos! Can you possibly cover problem #979?? It’s an interesting tree problem

[@eknathyadav8744]

The time complexity is O(m + n) amortized right ? btw great explanation as usual.

[@ameydhimte_c5956]

Nope its worst case think about it a bit Initially even I thought it would be O(n*m) for worst case but no... every element out of the m elements can be pushed/poped just once at most

[@thewanderingguy123]

Worst case scenario m = n so time complexity is O(n+n) = O(n)

[@tonyz2203]

what software do you use to draw?

[@NeetCode]

Paint3d

[@yuniorsanchez8578]

how can we code this "num1index = {n:i for i, n in enumerate(nums1)}" lets pythonic and more simple?

[@0Mynameisearl0]

For anyone else that still needs it: {key: value for value, key in enumerate(nums)}

[@JasonAhn-u5u]

@@0Mynameisearl0 Mind if I know why we're switching it around? Should it be {value: key for value, key in enumerate(nums)}?

[@neoncold2679]

Is this question supposed to be easy category? =(

[@nikhil199029]

Ut should be medium difficulty i think

[@ujjvalw2684]

how is that an "Easy" Question... maybe coding isnt for me lol

[@lb9gx]

Python brute force solution without using Hashmap. The idea I used here is to begin at the end of nums2 and iterate from there. class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: res = [1]*len(nums1) g = -1 for i in range(len(nums1)): for j in range(len(nums2) - 1, -1, -1): if nums2[j] > nums1[i]: g = nums2[j] if nums1[i] == nums2[j]: res[i] = g break g = -1 return res

[@ivanwen8335]

can you do "Next Greater Element II"?

[@__________________________6910]

Third bro

[@mrlectus]

How is this Easy?

[@abhishaiwinston9794]

First view

[@arijitsingh1096]

i dont think your explanation was correct at 9:10 where you said if you find the greatest element of first then you find the greatest elements for all between i think it is nott rue.. because let say [5 3 4 6] for 5- greatest element is 6 but for 3 it is not... (it is 4 for 3)...

[@necx5510]

my solution was O ( n * m) but still had the same runtime as your optimized code lmao

[@gianniprocida3332]

Thanks!