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.
@@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.
@@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...
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!
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!
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
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 🤔
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).
@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!
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
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?
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?
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!!!
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]
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?
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).
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.
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])
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
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!
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
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)...
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
You are the best explainer for leetcode problems bar none on the internet !!!! Wow .... !!! Thank you.
This is definitely not an easy problem!!
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.
@@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.
Yeah it did not feel easy to me
@@JustinK0 if you show up with the n^2 solution they won't hire you so no it is not easy ...
@@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...
Thanks!
Always enjoyable to watch your video solutions, thanks!
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!
Such a great explanationnnnnnn thankssssss 🙏🏼🙏🏼🙏🏼🙏🏼
Any better way to explain a LC problem than above can't be thought of, ever.Period!
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!
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
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 🤔
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
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).
ah nvm - I see, we compare each new value to the top of the stack to check if it's the next greater
How is this easy?!!
Same question
hey Neetcode, could you summarize all the questions you have done and make a leetcode list link to us? thx!
That would be amazing
Congratulations for 100k subscribers🎉🥳👏👏👏
@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!
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
Great explanation, with ur explanation feeling like it was so easy. Thank u so much
Perfect explanation. Very helpful. Thanks so much.
tbh this should be a medium question (without knowing the pattern), at least for the optimum solution.
def not an easy lol, great job as always
Agreed!
How did you calculate the space complexity for the stack part?
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?
as you have mentioned, there are 2 find operations in nums2, leading to (n * m * m).
@@akhilr94 the iteration over nums2 is the finding process so it will be O(n*m) not O(n*m*m)
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?
It won't 😢
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!!!
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??
2nd bro💓💓 lots of respect💥💥
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?
what software do you use to draw?
Paint3d
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]
Why cannot I first append element in stack, then while loop? The order makes a big difference, but I dont know the reason
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?
lmao
how can we code this "num1index = {n:i for i, n in enumerate(nums1)}" lets pythonic and more simple?
For anyone else that still needs it:
{key: value for value, key in enumerate(nums)}
@@0Mynameisearl0 Mind if I know why we're switching it around? Should it be {value: key for value, key in enumerate(nums)}?
question: why don't we directly loop num1?
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
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 ?
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).
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.
Great video
i love you neetcode
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])
bro sorting is O(nlogn)
thank you sir
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
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!
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??
I love your videos! Can you possibly cover problem #979?? It’s an interesting tree problem
Great video! Do you think you could cover #828 - Count Unique Characters?
The time complexity is O(m + n) amortized right ? btw great explanation as usual.
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
Worst case scenario m = n so time complexity is O(n+n) = O(n)
the easy are harder than some of the hards
The stack push op needs to be done unconditionally. The O(m+n) solution won't work as it is in the video.
n2 is fine, 😢 it ain't easy to lower complexity at easy level
Is this question supposed to be easy category? =(
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)...
What would be the solution if
nums2 = [5,1,6]
nums1 = [5,1]
This result=[6,6] or result = [-1,6] ?
[6,6] r8?
Ut should be medium difficulty i think
how is that an "Easy" Question... maybe coding isnt for me lol
can you do "Next Greater Element II"?
Third bro
How is this Easy?
First view
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
my solution was O ( n * m) but still had the same runtime as your optimized code lmao
Thanks!