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.
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
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;
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.
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!
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)
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
@@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!
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)
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.
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!
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
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?
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.
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.
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)?
🚀 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
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
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.
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.
Crazy. This channel explains coding solutions in the easiest way. It saves my life.
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!
did u make it into Google?
Man, we need more videos. Great production quality :)
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)
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 :)
I don't think if I'll ever see a better explanation to this problem. Kudos man!
It's funny how he always colors-in his arrow heads
Anyway, really cool insight about BFS!
Your videos and explanations are some of the best on RUclips, really great stuff man, keep it up!
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.
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.
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)
Drinking game: take a sip when he says "Right?"
The content of this channel is priceless. Been binge watching your videos
Please please man, I love your channel so much, you have never disappointed me. Make a list of important greedy problems please
I am new to serious coding but great job! this took me some time and now way close to this neatness level!
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!
Your explanation is too good! Understood it clearly.
This is the only one that I understood. Thanks a ton !
Happy to help!
question: why do we have to stop by the last_index - 1? while r < len(nums) - 1:
Searching the whole day and find this solution the best one 🙌🏼
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 😎
The best solution there is for this problem. I am saying after watching all other videos on this problem.🙌🙌
Thank You So Much for this wonderful video................🙏🙏🙏🙏🙏🙏
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.
one line should be added after updating j
i.e
if j
I love his patience and way of talking through the problem.
Your explanation and drawing is just awesome.
Nicely explained the intuition. Exactly wat i was looing for. Probably the best explanation in YT
Best channel for explaining the leetcode problems to a dumbo like me
One hell of an explanation ! Thank you
brilliant but I wouldnt be able to solve this by myself in a coding interview. Very clever indeed.
thank you code papi. i love you papi.
You are so good I just need to watch the explanation part and boom ! i can write my own code
great explanation and video! Espcially coloring. Unfortuntatelly does not work on leetcode any longer , giving timeout exceeded error.
9:28 Why
while r < len(nums) - 1
not
while r < len(nums)
?
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!
Awesome explanation!!
I did the regualr BFS and got stuck in a MLE error.
Now i know my mistakes.
Again Superb solution, which I was looking for! Thanks for this explanation.
really really good! Felt like one comment did not do justice to the level of simplicity!
You simply nailed it. Love from India ♥️
i don't know python still i watch all ur videos
Next level explanation of every approach
What an explanation. Loved it :)
I used a Dijkstra's approach to solve the problem, but this is a simpler and quicker answer... wow.
i tried this code but it somehow throws tle. would be glad if you let me know a little updation in the code. thanks
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
great explanation on the BFS mind behind the problem
what a beautiful piece of code
This explanation is crystal clear. Thank you!
Nice, looking at BFS for the first time in an array.
one of the best solution in internet for this question.
Thanks a lot!!
Your solutions are absolutely brilliant. I love the way you break down the solution with diagrams.
Thank you for the clear drawing explanation!
Thanks, happy it was helpful 🙂
Really neat code! Nicely done and explained.
Great Explanation !!!
You always have the simplest solution!
How is this solution a O(n)? Isnt there a for loop inside a while loop which makes it a O(n^2)?
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
This has got to be the best intuitive explanation out there for this problem
Excellent explanation. Much Thanks!
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?
No need, in the description it says that the solution existence is guaranteed.
Really good videos! Been watching alot of your videos lately! Thank you making such awesome videos!
Best explanation channels for python.
such a nice explanation. This video was so great. You earned a subscriber.
why left is re-initialised with only right +1, it can be moved to more than right +1?
i cant fathom how easily u did smthing i took hours and stil couldnt crack
Super clear explanation. Thanks!
this is nuts dawg, who allowed this to exist. im literally shaking and crying rn, wtf.
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
wow, BFS. Never thought it could be done like that
Why does the first time iterating through the array the for loop starts at 0 and goes to just the first index (0 + 1)?
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.
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.
Thank god for you!
bro is a genius
clearest explanation ever
Really elegant solution.
Awesome content as usual :)
You simplified it!! Thanks
Great video!
very clear explanation. Thank you!!
Best Solution explaination, thanks
I solved it in O(N^2) using DP.. I thought dp was supposed to be faster lol
Thank you for sharing. We can put farthest=0 before the while loop right?
Very good explanation!
Great explaination mate
Thanks.But I suppose the time should be O(n squares)
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)?
I have got the same doubt forloop inside while loop will give time complexity O(n^2) how does this become optimal solution?
@@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)
2 loops doesn't mean O(N^2)
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
Your the GOAT!
how would you come up with this in an interview, I could come up with the DP solution, but its n^2 complexity
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;
}
}
```
Best Explanation! Thanks
Why is the time complexity of DP step = O(n^2)?
great explanation! loved it