55.Jump Game
55. Jump Game
- You are given an integer array
nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. - Return
trueif you can reach the last index, orfalseotherwise.
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.
Method 1
【O(n) time | O(1) space】
package Leetcode.Greedy;
/**
* @author zhengstars
* @date 2024/06/14
*/
public class JumpGame {
public static boolean canJump(int[] nums) {
// Initialize the farthest position that can be reached
int maxReach = 0;
// Traverse the array
for (int i = 0; i < nums.length; i++) {
// If the current position is beyond the maxReach, it is not possible to continue
if (i > maxReach) {
return false;
}
// Update maxReach
maxReach = Math.max(maxReach, i + nums[i]);
// If maxReach is enough to reach the last position or beyond, return true
if (maxReach >= nums.length - 1) {
return true;
}
}
// After traversing, if still not able to reach the last position, return false
return false;
}
public static void main(String[] args) {
// Test case 1
int[] nums1 = {2, 3, 1, 1, 4};
System.out.println("Can jump for nums1: " + canJump(nums1)); // Expected output: true
// Test case 2
int[] nums2 = {3, 2, 1, 0, 4};
System.out.println("Can jump for nums2: " + canJump(nums2)); // Expected output: false
}
}
Enjoy Reading This Article?
Here are some more articles you might like to read next: