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; jumps++; } return jumps; }
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!
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)
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
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)
@@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!
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!
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.
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.
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
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)?
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
