Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A =[2,3,1,1,4]
, returntrue
.A =
[3,2,1,0,4]
, returnfalse
.Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A =[2,3,1,1,4]
The minimum number of jumps to reach the last index is
2
. (Jump1
step from index 0 to 1, then3
steps to the last index.)
Analysis
In Jump Game, we can save the farthest position we can reach when we go through the array. Every time we move, we will decrease the step. When we updating it, the step remaining for us is also updated. For example, for array A = [2, 3, 1, 1, 4], when we visit A[0], we update the maxReach to 2, and step to 2. When we visit A[1], we update maxReach to 1 + 3 = 4. And step is updated to 3. We will continue doing this until we reach the end or step getting to zero. If step getting to zero before we reach the end, it means that we can’t move forward so that we should return false.
In Jump Game II, we are asked for the minimum number of jumps. In fact, we only needs the number of jumps but not the path we jump. So that we can modify the code in Jump Game. We do not update step when we find a further position that we can reach. We only update it when step getting to 0. It means we can find the minimum number of jumps. In fact, in the test cases of this problem we can always reach the end. If we need to output -1 if we cannot reach the end, the code should be modified a little.
Code
Jump Game
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { public boolean canJump(int[] A) { if (A.length <= 1) return true; int maxReach = 0; int step = 1; for (int i = 0; i < A.length; i++) { step--; if (i + A[i] > maxReach) { maxReach = i + A[i]; step = A[i]; } if (step == 0 && i < A.length - 1) return false; } return true; } } |
Jump Game II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Solution { public int jump(int[] A) { if (A.length <= 1) return 0; int maxReach = A[0]; int step = A[0]; int jump = 1; for (int i = 1; i < A.length; i++) { if (i == A.length - 1) return jump; if (i + A[i] > maxReach) maxReach = i + A[i]; step--; if (step == 0) { jump++; step = maxReach - i; } } return jump; } } |
Complexity
We only go through the array once. So the complexity is only $O(n)$.