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 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
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!!!
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?
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?
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
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
@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
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!
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])
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...
How is this easy?!!
Same question
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!
Always enjoyable to watch your video solutions, thanks!
Such a great explanationnnnnnn thankssssss 🙏🏼🙏🏼🙏🏼🙏🏼
hey Neetcode, could you summarize all the questions you have done and make a leetcode list link to us? thx!
That would be amazing
Any better way to explain a LC problem than above can't be thought of, ever.Period!
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
Congratulations for 100k subscribers🎉🥳👏👏👏
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
def not an easy lol, great job as always
Agreed!
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 😢
Great explanation, with ur explanation feeling like it was so easy. Thank u so much
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?
tbh this should be a medium question (without knowing the pattern), at least for the optimum solution.
Thanks!
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!!!
Perfect explanation. Very helpful. Thanks so much.
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)
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?
lmao
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
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??
Why cannot I first append element in stack, then while loop? The order makes a big difference, but I dont know the reason
How did you calculate the space complexity for the stack part?
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 ?
what software do you use to draw?
Paint3d
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
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 stack push op needs to be done unconditionally. The O(m+n) solution won't work as it is in the video.
2nd bro💓💓 lots of respect💥💥
What would be the solution if
nums2 = [5,1,6]
nums1 = [5,1]
This result=[6,6] or result = [-1,6] ?
[6,6] r8?
the easy are harder than some of the hards
Is this question supposed to be easy category? =(
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)
thank you sir
Great video
@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
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)}?
n2 is fine, 😢 it ain't easy to lower complexity at easy level
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??
how is that an "Easy" Question... maybe coding isnt for me lol
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.
Ut should be medium difficulty i think
How is this Easy?
can you do "Next Greater Element II"?
Third bro
First view
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)
@@akhilr94 Counting Sort is O(n+m)
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!