Jump Game II - Greedy - Leetcode 45 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@dineshkumarkb1372]

All your videos are a treasure . Every single one is worth rewatching during interviews. Never ever delete these videos or stop uploading new ones.

[@naive-fleek7420]

during interviews??

[@dineshkumarkb1372]

@@naive-fleek7420 I meant during prep for interviews. It’s implied dude.

[@allen724]

This is a great explanation. I like this method better than LeetCode's published solution! It is more intuitive for me. Thanks and keep up these videos.

[@lakshmanprabhu6722]

Same here!. Went through a lot of solutions, but this is just gold.

[@ghdshds1899]

this explanation was actually dog

[@matthewtang1490]

Please don't stop making videos :) I just binged your DP playlist in 2 days

[@NeetCode]

Wow, I bet you would nail any interview now! Thanks for the kind words

[@crimsonghoul8983]

2 DAYS????

[@aniketyadav6247]

The below code also works : 1.) Traverse the entire nums array. On each i-th iteration, update the farthest_jump to the max of current value of farthest_jump and i + nums[i] 2.) If i is equal to the current jump we have completed the current jump and can now prepare to take the next jump (if required). So we increment the jump by 1 and set curr_jump to farthest jump. 3.) If that's not the case then do not update the jumps variable and the curr_jump variable since we haven't yet completed the current jump. 4.) In the end of the traversal you will get the minimum jumps. Hope this helps :) def jump(self, nums: List[int]) -> int: farthest_jump = 0 jump = 0 curr_jump = 0 for i in range(len(nums)-1): # Find the Farthest Jump farthest_jump = max(farthest_jump, i + nums[i]) # it means we have made the jump if i == curr_jump: # Point curr jump to the farthest jump curr_jump = farthest_jump jump += 1 return jump

[@venkateshnaidu2133]

Amazing solution, loved it! Here is a minor tweak to handle an edge case (no possible path) int minJumps(int arr[], int n){ // Your code here int l=0, r=0; int jumps = 0; while(r < n-1) { int farthest = 0; for(int i = l; i r) return -1; jumps++; } return jumps; }

[@akshatsamdani]

Thanks for posting this. I was thinking about the same

[@PorkBoy69]

The test cases are generated such that you can reach nums[n - 1].

[@PRAVEENKUMAR-fi1wu]

No need to do this. It is said in question. "We can always reach to the end" ​@@akshatsamdani

[@acala127]

This is the most elegant and clear explanation I have seen for this problem. Thank you!

[@karthikinamanamelluri7208]

Great explanation!! Even after this I was confused why the while condition is r < len(nums)-1, and not r < len(nums). I thought why can't we can change it to r < len(nums), and return res-1. This explains the algorithm better, since the result we are finding from the loop is the no. of blocks, and the no. of jumps is one less than no. of blocks. But this solution is not working for all the cases.

[@prashantgupta6160]

please continue this series, you are born to teach coding to other people.

[@heroicrhythms8302]

if we come to the middle of the array and can't reach the end anymore, that means we have encountered a 'zero'. then we should return -1. implement a check saying (if l>r: return -1)

[@licokr]

Crazy. This channel explains coding solutions in the easiest way. It saves my life.

[@ng.manisha]

You are literally a savior! I have my google interview lined up soon and all your videos actually teach me tricks how to think when faced with a problem!

[@iamnoob7593]

did u make it into Google?

[@protyaybanerjee5051]

Man, we need more videos. Great production quality :)

[@ma_sundermeyer]

Nice simplification of the BFS.. I had a similar idea but stayed with the conventional deque implementation: q = deque([(0,0)]) max_i = 1 while q: i,num_j = q.popleft() if i >= len(nums) - 1: return num_j for j in range(max_i, nums[i] + i + 1): q.append((j, num_j+1)) max_i = max(max_i, nums[i] + i + 1)

[@soumyajitganguly2593]

Great explanation man. Easy to generalize when jumping to last value is not possible.

[@denshaSai]

whats the reason that it is "while r < len(nums) - 1:" not just "while r < len(nums) :"?

[@arunavbhattacharya3353]

I fail to intuitively understand why do we need to iterate till n-1 instead of n

[@eternalmeme7920]

@@arunavbhattacharya3353 It's because, 1) All no. are positive, therefore if we touch the n-2 element, i.e. r=n-2, then we are iterating from l to r(inclusive), if we iterate at r=n-2, then since all no. positive, farthest will definitely be greater than >=n-1, therefore r

[@visase2036]

One of the main reasons for this is , Since we are accounting the 1st jump at position 0 , we are not considering the last element to calculate the answer ie [2,3,1,1,4] We re incrementing ans+1 by taking 2 into account , which is not necessary if you work logically and since we are accounting that as one jump we are ignoring the last element!

[@pruthvirajpatil7798]

Simple - Because if r is at len(nums)-1, we would have achieved the goal. No need to proceed ahead.

[@megavoltism]

It's funny how he always colors-in his arrow heads Anyway, really cool insight about BFS!

[@ge_song5]

question: why do we have to stop by the last_index - 1? while r < len(nums) - 1:

[@ssvivek4]

I don't think if I'll ever see a better explanation to this problem. Kudos man!

[@ekanshsharma1309]

why we write r < nums.size() - 1..... not just r< nums.size()??

[@RiteshThakur-o6r]

Because if r is at nums.size, then it has to terminate because it has reached the final index.

[@pranavmaiya4386]

hey did you get placed?

[@sniper324]

Your videos and explanations are some of the best on KZbin, really great stuff man, keep it up!

[@adityagoyal4299]

The content of this channel is priceless. Been binge watching your videos

[@darkexodus6404]

Your explanation is too good! Understood it clearly.

[@loia5tqd001]

9:28 Why while r < len(nums) - 1 not while r < len(nums) ?

[@abibhavankumar2522]

The array positions starts from 0 to length of array - 1. If you go till len(nums) then you will be considering an extra element that is not present in the array. Hope that clears your doubt!

[@divyanshkhetan]

This is a great approach. I especially liked how you related it to the concept of BFS. It helped in visualizing the approach so much!

[@ahmad3823]

I am new to serious coding but great job! this took me some time and now way close to this neatness level!

[@akshatgupta107]

Please please man, I love your channel so much, you have never disappointed me. Make a list of important greedy problems please

[@kashishsharma6809]

Oh man I unnecessarily used queue like in bfs. 🤧 I implemented exact bfs to find hops.. But using the interval instead of queue was awesome 😎

[@commandernorton88]

Drinking game: take a sip when he says "Right?"

[@bahaaiman8588]

This is the only one that I understood. Thanks a ton !

[@NeetCode]

Happy to help!

[@sagarnair9021]

one line should be added after updating j i.e if j

[@yathartharana7956]

Searching the whole day and find this solution the best one 🙌🏼

[@sauravchandra10]

Loved the analogy to BFS.

[@stith_pragya]

Thank You So Much for this wonderful video................🙏🙏🙏🙏🙏🙏

[@Gnaneshh]

One hell of an explanation ! Thank you

[@arunraj2527]

I love his patience and way of talking through the problem.

[@VarunMittal-viralmutant]

The standard solution for this question is like the LIS variant which is O(N**2). And that gives TLE on LeetCode I think the solution described above works only when it is guaranteed that the end can be reached, else it fails. Correct ? Modified to take care of unreachable cases: def find_shortest_jump_path(jumps): l, r = 0, 0 i = 0 res = 0 while l = len(jumps)-1 else -1

[@God0fSloth]

Thank you very much! Your code solved my problem. But what's the variable ( i ) used for? why are we increasing it?

[@VarunMittal-viralmutant]

@@God0fSloth That looks like some junk code, not used in final solution :)

[@venkatsaireddy1412]

why left is re-initialised with only right +1, it can be moved to more than right +1?

[@user-pn9sr2rq3z]

great explanation and video! Espcially coloring. Unfortuntatelly does not work on leetcode any longer , giving timeout exceeded error.

[@chandrachurmukherjeejucse5816]

Your explanation and drawing is just awesome.

[@dennisg3683]

Why does the first time iterating through the array the for loop starts at 0 and goes to just the first index (0 + 1)?

[@meghaldarji598]

The best solution there is for this problem. I am saying after watching all other videos on this problem.🙌🙌

[@vincenttung-or3ns]

This is freaking genius!

[@rohanb9512]

Nicely explained the intuition. Exactly wat i was looing for. Probably the best explanation in YT

[@ohmegatech666]

Just want to clarify that this is still a dynamic programming solution. That's because this solution is a moving window algorithm which are examples of dynamic programming. That is because they involve breaking the problem down into sub-problems and finding an optimal answer to those sub-problems, thus finding the optimal answer to the main problem. In this case the main problem is optimizing the fewest jumps to get to the end. The smaller sub-problem is finding the max jump within the current window.

[@themagickalmagickman]

I used a Dijkstra's approach to solve the problem, but this is a simpler and quicker answer... wow.

[@PrathamMittal-t8m]

Best channel for explaining the leetcode problems to a dumbo like me

[@tobito__]

How is this solution a O(n)? Isnt there a for loop inside a while loop which makes it a O(n^2)?

[@abhinav-lq9ms]

I think it's O(n) since we are always updating l to be r+1, so it won't again traverse the same value

[@krishnavamsichinnapareddy]

You simply nailed it. Love from India ♥️

[@hwang1607]

how would you come up with this in an interview, I could come up with the DP solution, but its n^2 complexity

[@pixelbyteee]

isn't this a O ( n^2 ) solution? as there are two loops? ( u mentioned it is an O ( n ) earlier )

[@697Alok]

What an explanation. Loved it :)

[@kevintran6102]

This explanation is crystal clear. Thank you!

[@MrExamer]

great explanation on the BFS mind behind the problem

[@aravinda1595]

You are so good I just need to watch the explanation part and boom ! i can write my own code

[@amarrajeev2903]

I think the edge cases also must be handled in the code. Suppose if the Algorithm could not find the minJumps it should return -1 as such. Thoughts on this?

[@markolainovic]

No need, in the description it says that the solution existence is guaranteed.

[@kewtomrao]

Awesome explanation!! I did the regualr BFS and got stuck in a MLE error. Now i know my mistakes.

[@xinniu3145]

Thank you for sharing. We can put farthest=0 before the while loop right?

[@shantanukumar4081]

Great Explanation !!!

[@ardhidattatreyavarma5337]

what a beautiful piece of code

[@shashijais789]

Again Superb solution, which I was looking for! Thanks for this explanation.

[@huatsai43]

Thank you for the clear drawing explanation!

[@NeetCode]

Thanks, happy it was helpful 🙂

[@VY-zt3ph]

Hello Neet!! You didn't mention the time coplexity here. Can uou please explain what was the time complexity? It seems it is n2 because of two nested loops. But I am still not sure.

[@111Apurva]

it's not n2 it is O(n) after calculating farthest you are not considering the element again (starting from r+1), In worst case of all 1's it would still go just once over each element

[@aishwaryaranghar3385]

i tried this code but it somehow throws tle. would be glad if you let me know a little updation in the code. thanks

[@sauravsingh7157]

It's giving TLE because this code goes in infinite loop in cases where we can't reach the end of the array. Ex- 1 2 0 0 6 7 - for this test case loop will never break. Here is a working code : def minJumps(self, arr, n): res = 0 l= r = 0 flag = 0 while r < len(arr) -1: farthest = 0 for i in range(l,r+1): farthest = max(farthest,i + arr[i]) l=r+1 r= farthest if l > r: flag =1 break res+=1 if flag ==1: return -1 return res

[@shantanushende6]

really really good! Felt like one comment did not do justice to the level of simplicity!

[@vishalmishra7018]

Really neat code! Nicely done and explained.

[@Cld136]

Excellent explanation. Much Thanks!

[@rabbyhossain6150]

Memory Complexity: O(n) class Solution: def jump(self, nums: List[int]) -> int: steps = 0 visited, q = set(), collections.deque() q.append(0) visited.add(0) while q: length = len(q) for _ in range(length): idx = q.popleft() if idx == len(nums) - 1: return steps for pos in range(1, nums[idx] + 1): if (idx + pos) not in visited: q.append(idx + pos) visited.add(idx + pos) steps += 1

[@rohands9195]

Why is the time complexity of DP step = O(n^2)?

[@supervince110]

You always have the simplest solution!

[@Kushagra_21]

one of the best solution in internet for this question. Thanks a lot!!

[@ankurtiwari5664]

i don't know python still i watch all ur videos Next level explanation of every approach

[@venkatrampramod7978]

Your solutions are absolutely brilliant. I love the way you break down the solution with diagrams.

[@gokulnaathbaskar9808]

Nice, looking at BFS for the first time in an array.

[@francescosacripante1661]

Correct me if I'm wrong, but couldn't we solve it by using Dijkstra algorithm? I mean we could create a graph and with this search for the shortest path to the end

[@shreshtashetty2985]

Nice solution, but how do you come up with this in an interview? In general, how do you tackle a greedy-solution problem?

[@darshansimha2166]

Nice video, I understand the solution. But I am having a tough time understanding the complexity for an array of all 1's wont the for loop inside run for every iteration in the array, so won't that make it O(n^2)?

[@divyasri9432]

I have got the same doubt forloop inside while loop will give time complexity O(n^2) how does this become optimal solution?

[@bmusuko]

​@@divyasri9432 I think the key here, we shift the left pointer to r+1 so we only inspect each element in the array once, it means it is o(n)

[@minhthinhhuynhle9103]

2 loops doesn't mean O(N^2)

[@user-2802cvsfkj]

this is nuts dawg, who allowed this to exist. im literally shaking and crying rn, wtf.

[@amrutaparab4939]

Thank god for you!

[@DivyaSingh-bl4cj]

Best explanation channels for python.

[@amanshaukat1105]

This is a great explanation. Very intuative. lets say it is not guaranteed that answer will exist, and we have to return -1 in such case. How could we handle this. Please help.

[@allwell8570]

You simplified it!! Thanks

[@algorithmo134]

@NeetCode Can we use a heap to find the maximum steps we can jump instead of looping over all the number of steps we can take and then finding the maximum?

[@oogieboogie7028]

TC of heap is n.logn. This approach is O(n)

[@thevagabond85yt]

I programmed by modifying Greedy Approach of Jump Game(I) : ``` class Solution { public int jump(int[] nums) { int N= nums.length, goal= N-1, jumpCount= 0; while(goal >0) { for(int i=0; i= goal) { goal= i; jumpCount++; break; } // if }//for }//while return jumpCount; } } ```

[@yashjain1011]

such a nice explanation. This video was so great. You earned a subscriber.

[@avishekarora]

Best Solution explaination, thanks

[@emekaobasi4765]

why till len(nums)-1, shouldn't it be len(nums) ?

[@peng943]

I don't get it neither... starting to hate myself when I can't understand something people don't think it is worthy to explain...

[@dent1808]

clearest explanation ever

[@trantung2013]

Really elegant solution.

[@gulershad4375]

def jump(nums): jump = 0 farthest = float('-inf') end = 0 for i in range(len(nums)): farthest = max(farthest, nums[i]) + 1 if i == end and i != len(nums) - 1: jump += 1 end = farthest return jump

[@sunshine-mc2oi]

Thank you for the awesome video. It's super easy to understand. Is there any chance you can make a video about 1326. Minimum Number of Taps to Open to Water a Garden and Video Stitching, they seem relevant to this topic. Thank you so much.

[@TheLaidia]

very clear explanation. Thank you!!

[@alonalon8794]

at the end of the algorithm r might point to an index which is lesser than the last index?

[@anupamdubey5736]

Best Explanation! Thanks

[@vasumahalingam5162]

brilliant but I wouldnt be able to solve this by myself in a coding interview. Very clever indeed.

[@LeCharles-bw4wp]

Thanks.But I suppose the time should be O(n squares)

[@MsSkip60]

Awesome content as usual :)

[@yifeicheng9102]

what's the time complexity of this solution?

[@swathiayas]

Really good videos! Been watching alot of your videos lately! Thank you making such awesome videos!

[@adwaitkesharwani3569]

Excellent explanation!!