Jump Game

How it works

We want to check if we can reach the last index starting from index 0.

Instead of trying all possible jumps, we can think about the problem in reverse:

• ask which positions can eventually reach the end
• then move backward to see if earlier positions can reach those positions

We keep a variable called goal:

• it represents the leftmost index that we must be able to reach
• initially, the goal is the last index itself

As we move backward through the array:

• if from index i we can jump to the current goal (or beyond), then index i becomes the new goal

At the end, if index 0 becomes the goal, it means we can reach the last index.

Steps

1. Initialize goal as the last index of the array.
2. Iterate from the second last index down to index 0.
3. For each index i:
   • Check if i + nums[i] >= goal
   • If yes, update goal = i because index i can reach the previous goal
4. After the loop finishes:
   • If goal == 0, return true
   • Otherwise, return false

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Confusing Jump Value with Index

The value nums[i] represents the maximum jump length, not the destination index. From position i, you can reach any index in [i + 1, i + nums[i]], not just i + nums[i]. Treating the jump value as a fixed destination misses valid shorter jumps.

Not Handling Zero Values Correctly

A zero at position i means you cannot move forward from that position. If all paths lead to a position with nums[i] == 0 before reaching the end, the answer is false. Ensure your algorithm properly detects when you are stuck.

Iterating in the Wrong Direction for Greedy

The greedy approach works backward, updating the goal position. A common mistake is iterating forward and incorrectly maintaining state. When going backward, the condition i + nums[i] >= goal correctly checks reachability.

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return goal == 0

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int goal = nums.size() - 1;

        for (int i = nums.size() - 2; i >= 0; i--) {
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }

        return goal == 0;
    }
};