45. Jump Game II & 55. Jump Game

 

 

 

 

 

 

 

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

 

class Solution {

public int jump(int[] nums) {

int n = nums.length;

if (n <= 1) return 0;

int maxReach = 0; // The farthest index we can currently reach

int curReach = 0; // The end of the current jump range

int jumps = 0; // Number of jumps made

for (int i = 0; i < n - 1; i++) {

maxReach = Math.max(maxReach, i + nums[i]);

if (i == curReach) {

jumps++;

curReach = maxReach;

if (curReach >= n - 1) {

break;

}

}

}

return jumps;

}

}

 

 

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

class Solution {

public boolean canJump(int[] nums) {

int maxReach = 0;

for(int i = 0;i < nums.length;i++){

if(i>maxReach){

return false;

}

maxReach = Math.max(maxReach,i + nums[i]);

}

return true;

}

}