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.

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

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

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

[@lil_jeke]

50 vidoes In 2 days?

[@acala127]

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

[@prashantgupta6160]

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

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

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

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

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

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

[@protyaybanerjee5051]

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

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

[@adityagoyal4299]

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

[@sagarnair9021]

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

[@Viso-code471]

for c++ -> int res = 0; int l = 0 , r = 0; int farthest = 0; while(r

[@arunraj2527]

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

[@darkexodus6404]

Your explanation is too good! Understood it clearly.

[@yathartharana7956]

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

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

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

[@anmolgupta945]

Also, isn’t it also 0(N^2) ? For loop inside while loop ?

[@megavoltism]

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

[@chandrachurmukherjeejucse5816]

Your explanation and drawing is just awesome.

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

[@meghaldarji598]

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

[@ge_song5]

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

[@venkatrampramod7978]

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

[@charan775]

This has got to be the best intuitive explanation out there for this problem

[@sniper324]

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

[@themagickalmagickman]

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

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

[@krishnavamsichinnapareddy]

You simply nailed it. Love from India ♥️

[@sauravchandra10]

Loved the analogy to BFS.

[@PrathamMittal-t8m]

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

[@MrExamer]

great explanation on the BFS mind behind the problem

[@kevintran6102]

This explanation is crystal clear. Thank you!

[@fahimislam9686]

can anyone tell me why r < len(nums)-1; cant it be r

[@Gnaneshh]

One hell of an explanation ! Thank you

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

[@stith_pragya]

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

[@bahaaiman8588]

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

[@NeetCode]

Happy to help!

[@rohanb9512]

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

[@user-pn9sr2rq3z]

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

[@shashijais789]

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

[@aravinda1595]

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

[@kewtomrao]

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

[@DivyaSingh-bl4cj]

Best explanation channels for python.

[@vincenttung-or3ns]

This is freaking genius!

[@supervince110]

You always have the simplest solution!

[@huatsai43]

Thank you for the clear drawing explanation!

[@NeetCode]

Thanks, happy it was helpful 🙂

[@gokulnaathbaskar9808]

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

[@ankurtiwari5664]

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

[@dent1808]

clearest explanation ever

[@697Alok]

What an explanation. Loved it :)

[@venkatsaireddy1412]

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

[@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; } } ```

[@shantanukumar4081]

Great Explanation !!!

[@ardhidattatreyavarma5337]

what a beautiful piece of code

[@Cld136]

Excellent explanation. Much Thanks!

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

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

[@Kushagra_21]

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

[@user-2802cvsfkj]

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

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

[@xinniu3145]

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

[@premthapa9959]

i cant fathom how easily u did smthing i took hours and stil couldnt crack

[@trantung2013]

Really elegant solution.

[@avishekarora]

Best Solution explaination, thanks

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

[@Kellykmixtape]

bro is a genius

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

[@allwell8570]

You simplified it!! Thanks

[@bibibaba2505]

best answer I have ever seen.

[@jhanvisaraswat6976]

wow, BFS. Never thought it could be done like that

[@vasumahalingam5162]

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

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

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

[@anupamdubey5736]

Best Explanation! Thanks

[@rohands9195]

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

[@appi147]

amazing explanation

[@SMAsaduzzamanAsad880]

Very good explanation!

[@TheLaidia]

very clear explanation. Thank you!!

[@yashjain1011]

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

[@LeCharles-bw4wp]

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

[@amrutaparab4939]

Thank god for you!

[@alonalon8794]

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

[@starkhunt2684]

Great explaination mate

[@subhajitrakshit9866]

Love this solution...Thanks

[@arihantjain3274]

Best explanation....

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

[@commandernorton88]

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

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

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