Jump Game 2 (LeetCode 45) | Minimum jumps to reach end of array

Jump Game 2 (LeetCode 45) | Minimum jumps to reach end of array | Explanation with Animations

Рет қаралды 27,980

Күн бұрын

To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
Actual problem on LeetCode: leetcode.com/problems/jump-ga...
Chapters:
00:00 - Intro
00:59 - Problem Statement
04:20 - How to approach?
08:13 - Greedy Solution
13:22 - Dry-run of Code
18:15 - Final Thoughts
📚 Links to topics I talk about in the video:
Jump Game: • Jump Game (LeetCode 55...
Dynamic Programming: • Dynamic Programming ea...
Greedy Algorithmic Paradigm: • Greedy Algorithms with...
Problems on Arrays: • Strings
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/3sJm8Wl
Favorite book to understand algorithms: amzn.to/4848xJH
Favorite book for data structures: amzn.to/3P96YBv
Get started for interview preparation: amzn.to/44Nn5du
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3PdsViT
Microphone: amzn.to/3Exv83x
Recording Camera: amzn.to/3PwyN8e
Tablet to sketch and draw: amzn.to/3ZdKVy7
Sketching Tool: amzn.to/45XJEgY
Laptop to edit videos: amzn.to/460ofDu
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

Пікірлер: 96

@luisguarin593 10 ай бұрын

Don’t stop what your doing. You’re amazing and i learn so much from you

@nilaxgajjar.work8 2 ай бұрын

This video's explanation was fantastic! I had a hard time grasping the concept of coverage before watching it, but your clear explanation and use of animations really helped me understand. The solution you presented visually, with both drawings and animations, made it much easier to follow along and almost had me solve the problem myself by the end. Thanks for such a well-done video! 🖊

@vinaysagar9280 4 ай бұрын

great explanation, easy to understand with your graphical representation. Keep doing what you're doing.

@hajeeramohamad7641 2 ай бұрын

Man!!! Hands down!!! You teach reallly well. The explanation was crystal clear. Even for the recursive brute force approach, your explanation was precise. Love it. Keep doing❤❤ Till date i find recursion very confusing. Please start a recursion playlist. The way you teach is very amazing. Gets right into the head. Would love to learn recursion from you.

@kalpitbansal9923 10 ай бұрын

Whenever I get stuck with a question, your videos always come to the rescue with clear and concise explanations. Your content has been a game-changer for my learning journey. Keep uploading more and more such tutorials.

@nikoo28 9 ай бұрын

will try my best to keep bringing useful content

@prakhargarg4166 7 ай бұрын

You explain so clearly

@raghebadel5689 6 ай бұрын

man you are so good, wish you all the best, all the love from Palestine

@anupamakovid4568 7 ай бұрын

excellent explanation 👌This is my first video on your channel, really loved the explanation. Subscribing !!

@nikoo28 6 ай бұрын

Thanks and welcome

@tasniatahsin8637 9 ай бұрын

your videos truly are helping me understand DSA so well! Keep it up

@nikoo28 9 ай бұрын

good luck 😇

@kamalasowmya7120 8 ай бұрын

great explanation Bhai! I watched the video so many times to get it. Finally was able to get the idea and solve it...Thanks for a thoughtful vid! :)

@parthchaudhary5134 9 ай бұрын

it's my first watch on your channel....u explains so good that i am subscribing you...and thank you soo much for educating us...

@nikoo28 9 ай бұрын

thanks for the sub :)

@abhaypatel379 26 күн бұрын

Excellent work 🎉

@janki-bx1rn 25 күн бұрын

literally the best explanation ever!

@aashanadhameja5754 10 ай бұрын

To the point explanation. Thanks!

@vikashaakash5202 4 ай бұрын

sir i dont know how but your solution help me to understand the problem very easy ur soln for each problem is unique and easy to understand

@DhananjayKumar-bd2jg 5 ай бұрын

great explanation!

@parthmodi2028 2 ай бұрын

great explaination !! u are too good

@Anonymous____________A721 Ай бұрын

Literally the best one

@tunebrotherdon 9 ай бұрын

Great explanation!

@AbhinavKumar-xo5ji 7 ай бұрын

Awsm explanation man

@itsmepratham2712 10 ай бұрын

Keep Going and Keep Posting

@ayushsharma5516 11 күн бұрын

usually i don't comment on videos but dudu u are amazing....so easily u have explained me......😇..u got a new subscriber

@nikoo28 11 күн бұрын

Thank you so much 😀

@mdshahidansari9126 Ай бұрын

Awesome explanation sir

@shubhamroy1094 9 ай бұрын

badiya samjhaya

@PrashantKumar-fk8le 10 ай бұрын

Great man

@m-bk4um 10 ай бұрын

simple and good

@raghavendravernekar4103 5 ай бұрын

nice explanation

@riyasharma-rn2ur 2 ай бұрын

Very good explanation sir

@nikoo28 2 ай бұрын

Thanks and welcome

@funnymoment9164 9 ай бұрын

Thanks!

@subee128 7 ай бұрын

Thanks

@basukinath2766 10 ай бұрын

thanks brother

@vanshsharma-lg1hj 2 ай бұрын

better than neetcode....for this soln presentation...thanku

@dnc077 2 ай бұрын

I like how you explained how to solve this with the greedy approach you have taken. The way you explain with images is really great. Thanks! I am experiencing a lot of difficulty reaching the solution. More than the coding, it's finding the solution that I am really struggling with. The approach I took for this case is consider the base case and move backwards. Somehow, I find it very difficult to find my way through it. I got very confused from that stage; I considered the recursive approach but did not have a clear picture in my mind how I was going to solve it. Then again, sometimes, I come across a problem where I literally do it with much less effort. I'm not sure if it's just me but I find myself unable to find the approach to solving the problem. Once I find the approach, the coding side is easy. I don't know - that's just me. Struggling but trying! :( Thanks for sharing.

@nikoo28 2 ай бұрын

I totally understand you. What you are experiencing is just a part of the coding journey. Always remember that it gets tough before it starts to get simpler. Just like you go on a hike...the start is very easy...then you begin to get tired, and it is hard to carry along. Once you cross that hurdle, the rest of the trek becomes enjoyable. :)

@nikoo28 2 ай бұрын

Keep doing what you are doing...as long as you are trying to write the solutions on your own rather than just copying the code, you will succeed :)

@wahid4544 7 ай бұрын

thanks for the helpful videos, what is the app name you use in your iPad to write and explain things?

@nikoo28 7 ай бұрын

GoodNotes 6

@sriyanandakuchimanchi4042 6 ай бұрын

beautiful beautiful

@SimpleCse2012 2 ай бұрын

Bhaiya in this code it would be if (lastIndex >= destination) { return totalJumps; } not Coverage>=destination

@udaykirankavaturu6942 8 ай бұрын

how to come up with such a greedy criteria, I mean what would be the thought process for a similar problem

@nikoo28 8 ай бұрын

as you solve more and more problems you will be able to narrow down some patterns. When starting any new problem, you will then try to get started with those known methods first. sometimes along the way, you will tweak them and discover new methods

@swarajgupta8646 4 ай бұрын

i have a doubt in if part that if take coverage as max at index 0 then we will reach at index 2 right which represents 1 at index 2 then if it is 1 then we can't choose 4 at index 1. Can anyone explain me that?? please help

@nikoo28 3 ай бұрын

Can you please elaborate on the doubt you have. I got confused

@saicharanpinninti548 5 ай бұрын

thank you so much exellent explanation and i have a small doubt there is a issue with your code if(coverage>+destination){ return total_jumps; } from above part of code you are returning without incerements total_jumps for last window i think and also there is a case entire window of elements is 0 then cant go the last_index right?

@sorrybhai100 5 ай бұрын

in leetcode there's a line which says "The test cases are generated such that you can reach nums[n - 1]". Means there will always be a way to reach the last index. So all 0 test cases won't be there. But it can be solved by putting checks for 0.

@nikoo28 4 ай бұрын

absolutely correct

@UtkarshOjha 9 ай бұрын

your code works perfectly on leetcode but not working on gfg, by the way great explanation

@nikoo28 8 ай бұрын

you may have to tweak it a little for the different problem constraints.

@michi19935 2 ай бұрын

Somehow, I had to replace coverage at the last if statemant with lastjumpInx because otherwise one jump was always missing: if(lastJumpIndx >= destination){ return totalJumps }

@shibhamalik1274 6 ай бұрын

Does the greed criteria say that choose the element with the max value from i till i+nums[i ] ? e.g 2,1,4,1,3,1,1,2 . for i =0 , nums[0 ] = 2, We choose 4 from 1,4. After that for i becomes 2 and for nums[2 ] = 4 we have options 1,3,1,1 and we chose max which is 3 and then reach in 3 min steps till the end. ?

@nikoo28 5 ай бұрын

every greed criteria will not give you the optimal solution. first we need to prove that the greed criteria we choose leads to an optimal solution. kzfaq.info/get/bejne/aa5iepZ82qvNgok.html

@mdshafiuddin1234 10 ай бұрын

Sir please make a playlist on advance recursion

@nikoo28 9 ай бұрын

will do

@mikeag1371 7 ай бұрын

I have an edge case - [ 2,16,1,2,3,1,1,2 ] here when i=1 coverage will be > destination hence return totaljumps which is 1 because i!=lastjump. but coverage>=destination so 1 will be returned but correct ans is 2 jumps because from 2->16->destination I am wrong ???

@nikoo28 7 ай бұрын

check the problem constraints on the actual problem page :)

@sahilsoni6339 10 ай бұрын

could you just check in the if condition where coverage>=destination at the place of coverage it will be lastIndex because if we return totalJumps without traversing till the lastIndex it will give wrong answer

@amritmohapatra8335 10 ай бұрын

right

@saicharanpinninti548 5 ай бұрын

yes before returning total_jumps need to increment

@CodeCraftAbhijit 4 ай бұрын

amz explanation

@035-harshitsingh7 6 ай бұрын

why we are using if(i==lastjumpindex) lastjumpindex= coverage; jumps++; can anyone explain?

@nikoo28 5 ай бұрын

did you follow the explanation? please don't jump straight to the code portion.

@nishanthsunkara1160 10 ай бұрын

I felt understanding coverage little tricky.

@nikoo28 9 ай бұрын

what part did you face a problem with?

@gangadharsai2705 6 ай бұрын

after ...coverage = max(coverage, i+arr[i]), add this if condition if(i>=coverage) return -1;// if you encounter any zero in between this edge case will help i.e., for test case: 3 2 1 0 5 code: int minJumps(vector &arr,int n) { // Write your code here. int totalJumps=0; int destination=n-1; int coverage=0; int lastJumpInd=0; if(n==1) return 0; for(int i=0;i=coverage) return -1; if(i==lastJumpInd){ lastJumpInd=coverage; totalJumps++; if(coverage>=destination) return totalJumps; } } return totalJumps; }

@vnn6568 4 ай бұрын

its failing for [2,3,1,1,4].

@nikoo28 3 ай бұрын

What answer are you expecting ?

@ago7506 6 ай бұрын

sir this code is not working it gives the wrong test cases in leetcode test case:[2,3,1,1,4] Output 1 Expected 2 .........code...... class Solution { public: int jump(vector& nums) { int jumps=0; int n=nums.size(); int coverage=0; int lastJump=0; int destination=n-1; if(n==1) return 0; for(int i=0;i=destination) { return jumps; } } return jumps; } };

@nikoo28 5 ай бұрын

you will need to debug the test case

@manvendrasingh4369 2 ай бұрын

There was few errors in your code but anyways nice explanation.

@nikoo28 2 ай бұрын

What errors did you find?

@nihal6636 9 ай бұрын

code is wrong it will always give one jump less than required jumps please check

@nikoo28 9 ай бұрын

did you try the code in the video description? it works perfectly on leetcode

@nihal6636 9 ай бұрын

@@nikoo28i got the answer already myself but thank u just need to replace coverage with lastjumpindex in last condition

@nigma933 4 ай бұрын

@@nihal6636 thank u!

@rajukachori9536 Ай бұрын

💥💥💥💥💥💥💥💥❤❤❤❤❤❤

@Udaylux 2 ай бұрын

Great explanation, but, the case for when the destination cannot be reached we should return -1 is not covered

@nikoo28 2 ай бұрын

if you check the problem constraints: "It's guaranteed that you can reach nums[n - 1]."

@nihal6636 9 ай бұрын

bro why u post video without veryfing the code just wasting our time and your time

@Sowmyakotha-lj8te 9 ай бұрын

Its perfectly working fine.If condition should be placed as shown below if(i==nextInterval){ nextInterval = coverage; jumps++; if(coverage >= target ){ return jumps; } }

@nikoo28 9 ай бұрын

the code works perfectly. Check the link in the description please :)

@ago7506 6 ай бұрын

thx buddy @@Sowmyakotha-lj8te

@piyushanand3451 4 ай бұрын

instead of if(coverage>= destination), there should be (lastjumpIdx>=destination)

@nikoo28 3 ай бұрын

Why do you think so?

@piyushanand3451 3 ай бұрын

@@nikoo28 N = 6 arr = {1, 4, 3, 2, 6, 7} Output: 2 take this example, if you are using coverage>= destination, your output will be 1.

@nikoo2805 3 ай бұрын

@@piyushanand3451i just verified. With my solution, the output is 2 as expected. Added a test case too to confirm. Look at the video description for the file. Make sure you are implementing it correctly :)