LeetCode 55. Jump Game (Algorithm Explained)
ฝัง
- เผยแพร่เมื่อ 2 ม.ค. 2020
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - วิทยาศาสตร์และเทคโนโลยี
That algorithm explanation section helps so much
That was some clean explanation Nick. I was aware of only the O(n2) solution. Keep it up.
This is simply beautiful! You've really taught me something on how to think about a solution approach! Thank you Nick!
Absolutely loved the explanation and how you broke it down into smaller sub problems! Superb stuff!
love the way you explain the code using dry runs
This is the best and easy-understanding solution I can tell. Thank you dude, excellent
Thank a bunch Nick, it was so much clearer after your explaining.
Love your video and the way you are talking dude!
Well the approach is so good and explained really well.Thanks Nick.
Probably your best explanation! Great video.
i was strugling with the sol from last 3 days but you made it clear in just 10 min kudos for your efforts
best explanation I have seen for this problem !! thanks Nick !
nick my brother you don't know how much ur videos help me in building approach and solving a problem. Your approach are always better than others please keep on making such videos.
Great explanation and beautiful code! Thanks Nick!
The explanation was awesome and you made it look easy. Thanks
Now that's a simple and efficient solution, combined with good explanation. I didn't even think of going backwards, just tried to brute-force it recursively.
then why is leetcode is not accepting the solution . its giving TLE
cuz recursive approach TS is in exponential form , which is uh.. really bad.. you can see the question's constraints.@@cindrasenareddy1929
Thanks for the explanation Nick. Nice approach. In case you have solved Leetcode 45 too (Jump Game II), could you share your solution?
how am i still covering the code...
Rookie mistake! Jk, no worries, still helpful.
Best explanation, clean and concise. thanks!
Nice Explanation. But technically I don't think we have to start from last Index as we are moving from behind and we dont care whats the value in the last index as we have reached there. (On line 4, we can start from lastGoodIndexPosition-1 (which is num.length-2))
Last good index means smallest index from which path to last index is possible
you are amazing bro, short and on-point. Perfect video :-)
really love your video, how is ur interview going so far?
This is actually quite neat. It only does whatever the questions asks.. nothing more. We don't really need to explore all possibilities when we only need to return whether or not it's possible to reach the last index. Cool solution this
Nick since the return type asked is boolean,keep the return values as true and false,other than i and 0. good explaination. understood it
Great strategy bro ! Sometimes those simple solutions can be hard to think of
Hey, do you also have a video for jump game 2?
good explanation! you should make a video about how you may not need leetcode for a dev job
@nick, Do you have a solution to Leetcode 45 with similar approach, where you start iterating from the right end of Index
This method seems a lot easier than trying to do it via DFS/Backtracking. You could also start the loop from "last_good_index_position -1" or nums.size()-2 as long as LGIP is initialized as nums.size()-1. It would mean one less loop required which probably makes minimal difference in terms of speed.
Yeah that's what I was thinking
Can you explain the minimum number of jumps (aka jump game ii) required to reach the end. @Nick
Wow.. Thanks a lot. Very clear explanation.
super easy to understand after watching your video!!
another great solution, sweet and simple.
thanks for the video, but your small rectangle bottom-left corner covers some of the code part/writing when you're explaining.
Nicely explained bro!!!
wow... the explaination, now this problem look really easy
clean, neat and easy to understand.
Really good Explanation
awesome Nick
Love your explanation!
Awesome 👍
Best in you tube one can find
the last index's value does not matter so we can skip it by doing nums.length -2 instead of nums.length -1 in the loop
the 'i + nums[i] >= lastGoodIndexPosition' part is hard to grasp initially until using a test case '2 0 0', now it clicks. thanks
I had a gut feeling there was some approach I could solve this starting at the last index, but I was unsure of that.
amazing explaination!!
Will you make one video on Jump Game 2 ?
Hi Nick ..I did not get why you have comapre i+nums[i] >= lastGoodIndexPosition....why not just to compare nums[i]
This is genius! Thanks a ton
nice explanation !
Amazing stuff. This is why I love solving problems. What I thought was a pretty straightforward backtracking question turned out to be a reverse linear traversal
Thank You So Much for this wonderful video...................🙏🙏🙏🙏🙏🙏
Amazing! Thannks!!
awesome Thank you
Really having trouble with all the interview problems. I need an explanation of how I can understand these algorithms
Please do Jump game II and Jump game III
why i + nums[i] >=. What is ">" doing here. Sorry could not understand that part
I have solved 70 easy questions and 5 medium questions on leetcode.. still can't think of these solutions.. born with a freezed mind! :/
Thank You!!
Nick
Spiral Matrix lll
🙏
Thnx Jonathan
I think this will work only for 1st index, will not work if i want jump from other index.
Ex a[]={2, 0, 1, 1, 4}, the code will true. where as it should fail when will start from index 1
The question is you have to start from 1st index.
How to know minimum number of steps
Did you come up with your solution on the fly during the video or did you solve the problem ahead of time?
I’ve solved this problem in a Coursera course I took before and it said I submitted a solution 10 months ago as well so I was pretty familiar with the problem
Nick White Felt slightly less dumb after reading your comment as my initial thinking while watching was to start from the beginning of the array...feeling dumb again after finding my previous comment was directly addressed at the end of the video. 🤣
Maybe try putting the video of yourself on screen right as it decreases the probability of it covering a line of code.
@@NickWhite Hey, by any chance, do you remember the name of that Coursera course? And/or do you have any other courses you recommend? Thanks!
@@NickWhite which coursera course did you took
Yes what was the Coursera course?
it's == at the return statement, but overall great explanation!
You can start the loop from "nums.length - 2" also. That will also be logically correct
not if nums[-2] is 0
what about the corner case then .where there is single entity in the array.
Damn. I thought the question was asking that you can ONLY jump the number of steps at nums[i]. But it actually means you can jump nums[i] or less. The solution for my former knocks out almost all test cases, but it is the wrong answer. Apparently, you have to do backtracking.
Brilliant.
Danke!
your algorithm was O(N), but your rambling goodbye was O(N^2)
I hate this question... It looks like Graph Search, It looks like back tracking... and then the answer is just reverse linear sweep...
you're too good at explaining it!
I din get how nums[i]+i is handling the logic
nums[i] is how many indices you can jump forward and i is the current index so it basically just tells you the farthest index you can jump from your current position
@@NickWhite Thanks! Appreciate the brief explanation. Understood now!
@@rupaldesai7098 Sometimes it helps to use descriptive local variables
int curMaxJump = nums[i];
if (i + curMaxJump >= lastGoodIndex)
Sometimes, you can give descriptive names to the 'magic numbers' in code:
final int EMPTY = 0, WALL = 1;
final int X = 0, Y = 1;
if (cell[X] == dest[X] && cell[Y] == dest[Y]) return true;
...
if (board[newRow][newCol] == WALL) continue;
This will help when you are reviewing your own code at a later date! :-)
I still don't understand how it works for the FALSE example.
nice
Eminem - Im the fastest rapper alive
Nick - Hey nick white here fndfsojdbfldmf.........
Never felt more stupid...damn it
please dry run this testcase [2,0,0] with your algo...
thanks :)
returns True
This will not work for many cases including [2,0,0]
It works
Comon bro. Use JavaScript ! I
This problem is not intuitive at all :((
srikrishna
6:42
the hate I have for this problem is unreal
Please dont cover text with your video. Thanks.
return nums[nums.length-2]!=0;
why not this one liner?