Problem Statement
You are given an integer array nums, where each element represents the maximum number of steps you can jump forward from that position.
Your task is to determine if you can reach the last index starting from the first index.

Example
Input: nums = [2, 3, 1, 1, 4]
Output: true
Explanation: Start at index 0, jump 1 step to index 1 (value = 3), then jump 3 steps to reach index 4.

Input: nums = [3, 2, 1, 0, 4]
Output: false
Explanation: You will get stuck at index 3 because it has value 0 and cannot move forward.

Understanding the Problem

At each position, the number tells you how far you can jump ahead. The challenge is to check whether there’s a path of jumps that reaches the end.

For example:

• From index 0 (value = 2), you can jump to index 1 or 2.
• From index 1 (value = 3), you can jump to 2, 3, or 4.

If any path allows reaching the last index, return true; otherwise, return false.

Thinking Process and Approach

Let’s think in simple terms:

1. You start at position 0.
2. Every time you move, you can reach a set of future positions based on how far you can jump.
3. You want to know whether there’s any reachable path that gets you to the last index.

A straightforward way would be trying all possibilities (recursion or backtracking), but that would be too slow (exponential time).
Instead, we can observe that we only need to know the farthest index we can reach at any point.

Greedy Approach

The most efficient way is a greedy approach:

1. Keep track of the farthest reachable index (maxReach).
2. Loop through the array, and for each index i:
   • If i is greater than maxReach, that means we can’t even reach this index — so return false.
   • Otherwise, update maxReach = max(maxReach, i + nums[i]).
3. If by the end of the loop maxReach is greater than or equal to the last index, return true.

Step-by-Step Example

Let’s take nums = [2, 3, 1, 1, 4]:

• Start with maxReach = 0.
• i = 0, nums[0] = 2
  → maxReach = max(0, 0 + 2) = 2
• i = 1, nums[1] = 3
  → maxReach = max(2, 1 + 3) = 4
• i = 2, nums[2] = 1
  → maxReach = max(4, 2 + 1) = 4

Since maxReach (4) ≥ last index (4), we can reach the end → true.

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

• i = 0, maxReach = 3
• i = 1, maxReach = 3
• i = 2, maxReach = 3
• i = 3, nums[3] = 0, maxReach = 3

When i moves to 4, it’s beyond maxReach, so we can’t reach → false.

Java Code Implementation

public class JumpGame {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            // If we cannot even reach index i, then return false
            if (i > maxReach) {
                return false;
            }
            // Update the farthest we can reach
            maxReach = Math.max(maxReach, i + nums[i]);
            // If we can already reach or go beyond the last index
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  We loop through the array once.
• Space Complexity: O(1)
  We only store one variable maxReach.

Key Takeaways

1. The greedy algorithm is the best way because you don’t need to try all jump combinations.
2. You only need to keep track of the farthest reachable index as you move.
3. If at any point you get stuck (can’t move forward), the answer is false.