Next Greater Element I - Leetcode 496 - Python

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 87

  • @vdyb745
    @vdyb745 2 роки тому +19

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

  • @smartsoothing776
    @smartsoothing776 Рік тому +72

    This is definitely not an easy problem!!

    • @JustinK0
      @JustinK0 9 місяців тому

      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
      @chrischika7026 8 місяців тому +27

      @@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
      @berserker556 7 місяців тому +1

      Yeah it did not feel easy to me

    • @thebigpart783
      @thebigpart783 6 місяців тому

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

    • @cicakmuhamed
      @cicakmuhamed 4 місяці тому +10

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

  • @andreytamelo1183
    @andreytamelo1183 2 роки тому +7

    Thanks!

  • @lingxu9697
    @lingxu9697 2 роки тому +8

    Always enjoyable to watch your video solutions, thanks!

  • @foofoo17
    @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!

  • @ingluissantana
    @ingluissantana 2 роки тому +8

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

  • @manjultripathi8309
    @manjultripathi8309 Рік тому

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

  • @paul_tee
    @paul_tee Рік тому +3

    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!

  • @transgenicznyogorek
    @transgenicznyogorek 9 місяців тому

    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-b5r
    @Arnaud-b5r 29 днів тому

    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
    @gauravmasand 3 місяці тому

    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

  • @dp2120
    @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
      @dp2120 Місяць тому

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

  • @taiwoadebisi9315
    @taiwoadebisi9315 Рік тому +37

    How is this easy?!!

  • @chankwongyin7455
    @chankwongyin7455 2 роки тому +14

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

    • @lex-zt6uc
      @lex-zt6uc 2 роки тому

      That would be amazing

  • @polasumanth9826
    @polasumanth9826 2 роки тому +2

    Congratulations for 100k subscribers🎉🥳👏👏👏

  • @JasonAhn-u5u
    @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
      @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

  • @shalinisangal84
    @shalinisangal84 7 місяців тому

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

  • @tamarehrenreich7428
    @tamarehrenreich7428 Рік тому

    Perfect explanation. Very helpful. Thanks so much.

  • @jasonl.7466
    @jasonl.7466 2 роки тому +3

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

  • @cc-to2jn
    @cc-to2jn 2 роки тому +14

    def not an easy lol, great job as always

  • @avinashtiwari4025
    @avinashtiwari4025 Рік тому

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

  • @memeproductions4182
    @memeproductions4182 2 роки тому +1

    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
      @akhilr94 2 роки тому

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

    • @faithcyril513
      @faithcyril513 Рік тому

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

  • @akhilr94
    @akhilr94 2 роки тому +3

    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?

  • @ninjacloud4748
    @ninjacloud4748 2 роки тому

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

  • @niharikkatyagi4089
    @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??

  • @Vishal_84_k
    @Vishal_84_k 2 роки тому +1

    2nd bro💓💓 lots of respect💥💥

  • @zhonglingsun6743
    @zhonglingsun6743 2 роки тому +1

    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?

  • @tonyz2203
    @tonyz2203 2 роки тому +1

    what software do you use to draw?

  • @iliauk1
    @iliauk1 2 роки тому

    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]

  • @lingyuhu4623
    @lingyuhu4623 2 роки тому

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

  • @orangethemeow
    @orangethemeow 2 роки тому +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?

  • @yuniorsanchez8578
    @yuniorsanchez8578 2 роки тому

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

    • @0Mynameisearl0
      @0Mynameisearl0 2 роки тому

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

    • @JasonAhn-u5u
      @JasonAhn-u5u Рік тому

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

  • @SnowdenFu-jh6bx
    @SnowdenFu-jh6bx Місяць тому

    question: why don't we directly loop num1?

  • @whathappened2872
    @whathappened2872 2 роки тому

    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

  • @marlieemam216
    @marlieemam216 2 роки тому

    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 ?

  • @leventoz9530
    @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
      @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.

  • @kirillzlobin7135
    @kirillzlobin7135 11 місяців тому

    Great video

  • @hasferrr
    @hasferrr 2 місяці тому

    i love you neetcode

  • @davyroger3773
    @davyroger3773 2 роки тому

    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
      @akhilr94 2 роки тому +1

      bro sorting is O(nlogn)

  • @sanooosai
    @sanooosai 10 місяців тому

    thank you sir

  • @zergenzerg6853
    @zergenzerg6853 2 роки тому

    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

  • @ibrahimmalik4155
    @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
      @olawaleojodu6704 4 місяці тому

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

  • @junkim4323
    @junkim4323 2 роки тому

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

  • @droft1312
    @droft1312 2 роки тому

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

  • @eknathyadav8744
    @eknathyadav8744 2 роки тому

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

    • @ameydhimte_c5956
      @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
      @thewanderingguy123 Рік тому

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

  • @greatestever2914
    @greatestever2914 2 роки тому +1

    the easy are harder than some of the hards

  • @samagrasinghtomar79
    @samagrasinghtomar79 3 місяці тому

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

  • @atifzia124
    @atifzia124 3 місяці тому

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

  • @neoncold2679
    @neoncold2679 2 роки тому

    Is this question supposed to be easy category? =(

  • @arijitsingh1096
    @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)...

  • @ruchitagarde4642
    @ruchitagarde4642 5 місяців тому

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

  • @nikhil199029
    @nikhil199029 2 роки тому

    Ut should be medium difficulty i think

  • @ujjvalw2684
    @ujjvalw2684 Рік тому +1

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

  • @ivanwen8335
    @ivanwen8335 2 роки тому

    can you do "Next Greater Element II"?

  • @__________________________6910
    @__________________________6910 2 роки тому

    Third bro

  • @mrlectus
    @mrlectus Рік тому

    How is this Easy?

  • @abhishaiwinston9794
    @abhishaiwinston9794 2 роки тому

    First view

  • @lb9gx
    @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

  • @necx5510
    @necx5510 Рік тому

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

  • @gianniprocida3332
    @gianniprocida3332 2 роки тому +2

    Thanks!