Jump Game

Share

Given array of jump lengths at each position, determine if you can reach the last index.

Example 1
Input: nums=[2,3,1,1,4] → Output: true
Example 2
Input: nums=[3,2,1,0,4] → Output: false

Solution Approach

Track the maximum reachable index. If current index exceeds it, stuck.

  • Track maxReach = 0
  • For each index i from 0 to n-1
  • If i > maxReach return false
  • Update maxReach = max(maxReach, i + nums[i])
  • Return true
Java
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;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)