Jump Game II - Greedy - Leetcode 45 - Python
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/jump-gam...
0:00 - Read the problem
2:06 - Drawing Explanation
7:05 - Coding Explanation
leetcode 45
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #python - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
All your videos are a treasure . Every single one is worth rewatching during interviews. Never ever delete these videos or stop uploading new ones.
during interviews??
@@naive-fleek7420 I meant during prep for interviews. It’s implied dude.
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.
Same here!. Went through a lot of solutions, but this is just gold.
Please don't stop making videos :) I just binged your DP playlist in 2 days
Wow, I bet you would nail any interview now! Thanks for the kind words
2 DAYS????
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
This is the most elegant and clear explanation I have seen for this problem. Thank you!
please continue this series, you are born to teach coding to other people.
Man, we need more videos. Great production quality :)
Your videos and explanations are some of the best on CZcams, really great stuff man, keep it up!
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!
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;
}
Thanks for posting this. I was thinking about the same
The test cases are generated such that you can reach nums[n - 1].
No need to do this. It is said in question. "We can always reach to the end" @@akshatsamdani
Crazy. This channel explains coding solutions in the easiest way. It saves my life.
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!
I am new to serious coding but great job! this took me some time and now way close to this neatness level!
I don't think if I'll ever see a better explanation to this problem. Kudos man!
I love his patience and way of talking through the problem.
Nicely explained the intuition. Exactly wat i was looing for. Probably the best explanation in YT
Really good videos! Been watching alot of your videos lately! Thank you making such awesome videos!
This explanation is crystal clear. Thank you!
Really neat code! Nicely done and explained.
One hell of an explanation ! Thank you
Please please man, I love your channel so much, you have never disappointed me. Make a list of important greedy problems please
The content of this channel is priceless. Been binge watching your videos
What an explanation. Loved it :)
one of the best solution in internet for this question.
Thanks a lot!!
Excellent explanation. Much Thanks!
The best solution there is for this problem. I am saying after watching all other videos on this problem.🙌🙌
Searching the whole day and find this solution the best one 🙌🏼
It's funny how he always colors-in his arrow heads
Anyway, really cool insight about BFS!
Your explanation is too good! Understood it clearly.
very clear explanation. Thank you!!
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.
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)
Super clear explanation. Thanks!
This is the only one that I understood. Thanks a ton !
Happy to help!
You are so good I just need to watch the explanation part and boom ! i can write my own code
Awesome content as usual :)
Again Superb solution, which I was looking for! Thanks for this explanation.
Thank you for the clear drawing explanation!
Thanks, happy it was helpful 🙂
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)
such a nice explanation. This video was so great. You earned a subscriber.
great explanation! loved it
You simply nailed it. Love from India ♥️
best explanation! Thank you so much!
Great Explanation !!!
Best Explanation! Thanks
great explanation on the BFS mind behind the problem
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
Thank you very much! Your code solved my problem.
But what's the variable ( i ) used for? why are we increasing it?
@@God0fSloth That looks like some junk code, not used in final solution :)
Excellent explanation!!
What a great explaination!
Your explanation and drawing is just awesome.
Awesome explanation!!
I did the regualr BFS and got stuck in a MLE error.
Now i know my mistakes.
Great explaination mate
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 😎
You always have the simplest solution!
Keep Rocking !!
really really good! Felt like one comment did not do justice to the level of simplicity!
Great video!
question: why do we have to stop by the last_index - 1? while r < len(nums) - 1:
You simplified it!! Thanks
amazing! subscribed
Love this solution...Thanks
Really elegant solution.
Best Solution explaination, thanks
GREAT thanks a lot!
one line should be added after updating j
i.e
if j
i don't know python still i watch all ur videos
Next level explanation of every approach
Fantastic!!
9:28 Why
while r < len(nums) - 1
not
while r < len(nums)
?
Thank god for you!
Thank You So Much for this wonderful video................🙏🙏🙏🙏🙏🙏
Nice, looking at BFS for the first time in an array.
Best explanation channels for python.
clearest explanation ever
what a beautiful piece of code
Your the GOAT!
Amazing 🔥
Thank you for sharing. We can put farthest=0 before the while loop right?
Awesome explanation
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.
Best channel for explaining the leetcode problems to a dumbo like me
whats the reason that it is "while r < len(nums) - 1:" not just "while r < len(nums) :"?
I fail to intuitively understand why do we need to iterate till n-1 instead of n
@@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
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!
Simple - Because if r is at len(nums)-1, we would have achieved the goal. No need to proceed ahead.
Great explanation
How is this solution a O(n)? Isnt there a for loop inside a while loop which makes it a O(n^2)?
Thank you so much
why we write r < nums.size() - 1.....
not just r< nums.size()??
Because if r is at nums.size, then it has to terminate because it has reached the final index.
Why does the first time iterating through the array the for loop starts at 0 and goes to just the first index (0 + 1)?
@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?
TC of heap is n.logn. This approach is O(n)
amazing explanation
thank you!
brilliant but I wouldnt be able to solve this by myself in a coding interview. Very clever indeed.
Well explained
I used a Dijkstra's approach to solve the problem, but this is a simpler and quicker answer... wow.
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.
Man I have to say "Bravo"!
how would you come up with this in an interview, I could come up with the DP solution, but its n^2 complexity
Best explanation....
Masterpiece.
thank you code papi. i love you papi.
Legendary!!!!