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 true if you can reach the last index, or false otherwise.

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.

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

Approach: Greedy (Maximum Reachable Index)

Algorithm

1. Maintain maxReach, the farthest index reachable so far
2. Iterate through the array; if the current index is beyond maxReach, return false
3. Otherwise update maxReach = max(maxReach, i + nums[i])
4. If maxReach reaches or exceeds the last index, return true

Time & Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - constant extra space

Java Implementation

public class JumpGame {

    /**
     * Determine whether the last index can be reached.
     * @param nums Maximum jump length at each position
     * @return true if the last index is reachable
     */
    public static 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;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 1, 4};
        System.out.println("Input: nums = [2, 3, 1, 1, 4]");
        System.out.println("Output: " + canJump(nums1)); // Expected: true

        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println("Input: nums = [3, 2, 1, 0, 4]");
        System.out.println("Output: " + canJump(nums2)); // Expected: false
    }
}

Example Walkthrough

For nums = [2, 3, 1, 1, 4]:

1. i=0, num=2: maxReach = max(0, 0+2) = 2
2. i=1, num=3: maxReach = max(2, 1+3) = 4 (last index already reachable)
3. i=2, num=1: maxReach = max(4, 2+1) = 4
4. i=3, num=1: maxReach = max(4, 3+1) = 4
5. i=4, num=4: maxReach = max(4, 4+4) = 8

Result: true.

For nums = [3, 2, 1, 0, 4]:

1. i=0, num=3: maxReach = 3
2. i=1, num=2: maxReach = 3
3. i=2, num=1: maxReach = 3
4. i=3, num=0: maxReach = 3
5. i=4: i=4 > maxReach=3, so return false

Key Points

1. Greedy Choice: Only the farthest reachable index matters, not the exact path
2. No Backtracking: There is no need to simulate every jump combination
3. Early Termination: The loop can stop as soon as maxReach >= nums.length - 1
4. O(1) Space: Only a single variable is required
5. Edge Case: A zero in the middle may block progress if it is not reachable past