Understanding Jump Game in Java

Introduction & Problem Explanation

The Jump Game problem gives us an integer array nums. We start at the array's first index, and each element in the array represents your maximum jump length at that position.

Our goal is to determine if we can reach the last index of the array. For example, given nums = [2, 3, 1, 1, 4], we return true. We jump 1 step from index 0 to index 1, then jump 3 steps to the last index. Conversely, for nums = [3, 2, 1, 0, 4], we return false. Regardless of how we jump, we always land at index 3, where the maximum jump length is 0, leaving us stranded. Although we could explore this using dynamic programming, we can solve it in a highly optimized linear time using a greedy reachability scan.

The Algorithmic Approach

Greedy Reachability Scan (O(n) Time, O(1) Space)

Instead of tracking all paths, we only care about the furthest index we can possibly reach at any point in time. We maintain a variable reachable initialized to 0. As we scan the array from left to right:

• Check Feasibility: If our current index i is greater than reachable, it means we have walked to a position that we can never actually reach. In this case, we immediately return false.
• Update Reach: Otherwise, we update our maximum reach. From index i, we can jump up to nums[i] steps forward. Therefore, the furthest index we can reach from this point is i + nums[i]. We update reachable = Math.max(reachable, i + nums[i]).
• Early Termination: If at any point reachable is greater than or equal to the last index (nums.length - 1), we can stop early and return true.

If the loop completes successfully, it means we were able to navigate the entire array, so we return true.

Step-by-Step Execution Walkthrough

Let's trace the greedy scan for nums = [2, 3, 1, 0, 4]:

1. Step 1 (Initialization): Set reachable = 0.
2. Step 2 (Index 0: val = 2):
   • Is 0 > reachable? No.
   • Update reach: reachable = Math.max(0, 0 + 2) = 2.
   • Current state: reachable = 2.
3. Step 3 (Index 1: val = 3):
   • Is 1 > reachable (2)? No.
   • Update reach: reachable = Math.max(2, 1 + 3) = 4.
   • Furthest index is 4. Since 4 >= nums.length - 1 (which is 4), we stop early and return true!

Now, let's trace a failing case nums = [1, 0, 2]:

1. Step 1 (Initialization): Set reachable = 0.
2. Step 2 (Index 0: val = 1):
   • Is 0 > 0? No.
   • Update reach: reachable = Math.max(0, 0 + 1) = 1.
3. Step 3 (Index 1: val = 0):
   • Is 1 > 1? No.
   • Update reach: reachable = Math.max(1, 1 + 0) = 1.
4. Step 4 (Index 2: val = 2):
   • Is 2 > reachable (1)? Yes. Index 2 is unreachable because we are stuck at index 1.
   • Return false.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• if (i > reachable) return false;: The fail-fast check. If our current index exceeds our maximum possible reach, the game is over and we can never progress.
• Math.max(reachable, i + nums[i]): The greedy choice. We update our horizon by choosing the largest reach possible.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class JumpGame {

    // Greedy Reachability: Time O(N), Space O(1)
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int reachable = 0;
        int target = nums.length - 1;

        for (int i = 0; i < nums.length; i++) {
            // If the current index is unreachable, we are stuck
            if (i > reachable) {
                return false;
            }

            // Update the furthest index we can reach
            reachable = Math.max(reachable, i + nums[i]);

            // Early exit if we can already reach the destination
            if (reachable >= target) {
                return true;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        JumpGame solver = new JumpGame();
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};

        System.out.println("--- Jump Game Demonstration ---");
        System.out.println("Scenario 1: " + Arrays.toString(nums1));
        System.out.println("Can reach end: " + solver.canJump(nums1)); // Expected: true

        System.out.println("\nScenario 2: " + Arrays.toString(nums2));
        System.out.println("Can reach end: " + solver.canJump(nums2)); // Expected: false
    }
}

Conclusion

The Jump Game showcases the power of Greedy Algorithms. By only tracking the absolute furthest reach instead of exploring every path, we reduce an exponential search space to a single linear scan requiring zero auxiliary memory.