In algorithmic design, optimization problems often tempt us to map out every possible decision path. A classic example is the Jump Game problem (popularized on LeetCode). You are given an integer array nums, representing a linear path of stepping stones. Starting at index 0, each stone contains a value indicating the maximum number of steps you can jump forward from that position. Your objective is simple: determine if it is mathematically possible to reach the final index.

At first glance, this looks like a problem for back-tracking or dynamic programming (DP). An explorer might list every single jump combination to search for a path. However, exploring all paths takes exponential time ($O(2^n)$), and even dynamic programming requires quadratic time ($O(n^2)$) and linear auxiliary space. By framing the problem around reachability, we can solve it in a single linear scan ($O(n)$ time) with constant auxiliary space ($O(1)$) using a greedy strategy. In this article, we will unpack this greedy reachability scan.

Real-World Analogy: The Electric Vehicle Highway

To understand greedy reachability, imagine driving an electric car along a remote highway:

  • The Charging Stations: Each index in the array is a mile marker with a battery charging station. The value at that station represents the maximum distance the charger can add to your range.
  • The Horizon: As you drive, you do not need to calculate every possible route. You only need to track the furthest mile marker you can reach on your current charge (your horizon).
  • Getting Stranded: If you arrive at a mile marker that is further than your vehicle's maximum possible range, you run out of charge and get stranded. You return false.
  • Destination Achieved: If your horizon ever equals or exceeds the final destination, you know for a fact you can make it, and you return true.
In this system, you do not track every road; you simply look at how far your fuel can carry you.

Greedy Scan Logic & Mechanics

Our greedy algorithm scans the array from left to right while updating our horizon, which we store in a variable called reachable (initialized to 0). At each step:

  1. The Stranded Check: If the current index i is greater than reachable, we have crossed our maximum possible horizon, meaning we are stuck. We immediately return false.
  2. The Horizon Update: Otherwise, from the current index i, we can jump up to nums[i] steps. The furthest point reachable from here is i + nums[i]. We update our horizon using reachable = Math.max(reachable, i + nums[i]).
  3. Early Exit: If reachable is greater than or equal to the last index, we exit early and return true.

Execution Trace Examples

Let's trace two scenarios to see the reachability logic in action:

Scenario A: Success Case [2, 3, 1, 1, 4]

  • Start: reachable = 0.
  • Index 0 (val = 2): i is not greater than reachable. We update reachable = Math.max(0, 0 + 2) = 2.
  • Index 1 (val = 3): i (1) is within range. We update reachable = Math.max(2, 1 + 3) = 4.
  • Target index is 4. Since reachable (4) >= target (4), we terminate early and return true!

Scenario B: Failure Case [3, 2, 1, 0, 4]

  • Start: reachable = 0.
  • Index 0 (val = 3): reachable becomes 3.
  • Index 1 (val = 2): reachable becomes Math.max(3, 1 + 2) = 3.
  • Index 2 (val = 1): reachable becomes Math.max(3, 2 + 1) = 3.
  • Index 3 (val = 0): reachable becomes Math.max(3, 3 + 0) = 3.
  • Index 4 (val = 4): i (4) > reachable (3). The loop detects that index 4 is completely unreachable. We return false.

Java Solution 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 & Algorithm Takeaways

The Jump Game demonstrates the elegance of greedy algorithms. By shifting our perspective from "how do I get there?" (pathfinding) to "how far can I possibly go?" (reachability), we compress a complex exponential tree into a single, lightning-fast linear scan requiring zero auxiliary memory.