Linear time algorithm for Minimum number of jumps required to reach end
algorithm, c, data-structures, dynamic-programming
Solution
Summary of your algorithm:
- Take the first item and look how far you can get with this (incrementing `i` until `arr[j]+j < i`)
- Go to the next item that you can reach from the first one and that takes you at least to `i`th item.
- Repeat this until you reach the last entry.
First: Yes it runs in `O(n)` since the algorithm pushes both `i` an `j` only one time from `1` to `n` in worst case.
Second I have not seen a proof that `O(n²)` is the optimal time-complexity.
Thrid You can visualize the `arr` like this so this is exactly what your algorithm does. You can use this to proof by induction that your algorithm is correct. But as @Leo mentioned, there has to be a solution.
Fix for no-solution-case Make sure that `j < i` holds.
Problem
Problem: Minimum number of jumps to reach end Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element. Example: Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} Output: 3 (1-> 3 -> 8 ->9) First element is 1, so can only go to 3. Second element is 3, so can make at most 3 steps i.e. to 5 or 8 or 9. Source: http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/ I have made a linear time algorithm for finding Minimum number of jumps required to reach end of an array. The source code is as below: ``` int minJumpsUpdated(int arr[], int n) { int *jumps = malloc(n * sizeof(int)); // jumps[n-1] will hold the result int i =1, j = 0; jumps[0] = 0; for (i = 1; i < n; ) { // if i is out of range of arr[j], then increment j if (arr[j] + j < i && j < i) { j++; // else if i is within range of arr[j], // jumps for ith element would be jumps[j]+1 } else if (arr[j] + j >= i && j < i) { jumps[i] = jumps[j] + 1; i++; } else { printf("solution does not exist"); return -1; } } printf("jumps: "); for (i = 0; i < n; i++) { printf("%d, ", jumps[i]); } return jumps[n - 1]; } ``` Example: 1.) initially `i=1, j=0` and `arr[] = {1, 3, 6, 1, 0, 9};` ``` jumps[] = 0,0,0,0,0,0 ``` 2.) as `i` is within range of `arr[j]` ie. `i<= j+arr[j]`, number of jumps required to go to ith position would be min number of jumps till jth position + 1. ``` i=2, j=0, jumps[] = 0,1,0,0,0,0 ``` 3.) `i>j+arr[j]` i.e. `j++;` ``` i=2, j=1, jumps[] = 0,1,0,0,0,0 ``` 4.) `i<=j+arr[j]` i.e. `jumps[i] = jumps[j]+1;` ``` i=3, j=1, jumps[] = 0,1,2,0,0,0 ``` 5.) `i<=j+arr[j]` i.e. `jumps[i] = jumps[j]+1;` ``` i=4, j=1, jumps[] = 0,1,2,2,0,0 ``` 6.) `i<=j+arr[j]` i.e. `jumps[i] = jumps[j]+1;` ``` i=5, j=1, jumps[] = 0,1,2,2,2,0 ``` 7.) `i>j+arr[j]` i.e. `j++;` ``` i=5, j=2, jumps[] = 0,1,2,2,2,0 ``` 8.) `i<=j+arr[j]` i.e. `jumps[i] = jumps[j]+1;` ``` i=6, j=2, jumps[] = 0,1,2,2,2,3 ``` ------ END ------ I am not able to figure out under which test case this program will not work. I am asking this because on internet the optimized solution is using DP which is O(n^2). My solution is linear time. i.e. O(n). So I am assuming there are some cases which this algorithm will not handle. So I am curious what cases it does not handle. Your help will be appreciated. Thank you.