52. Jump Game

Try every possible jump from each position recursively. If any path reaches the last index, return true.

Brute Force

From the current position, try every jump length from 1 to nums[current]. Recursively check if any of those positions can reach the end.

This explores all possible paths, leading to O(2^n) time in the worst case because each position can branch into multiple sub-problems. Space is O(n) for the recursion stack.

Why it is slow: Many positions are revisited across different paths, and the exponential branching makes it impractical for large inputs.

import java.util.*;

class Solution {
    public boolean canJump(int[] nums) {
        Boolean[] memo = new Boolean[nums.length];
        return dfs(nums, 0, memo);
    }

    private boolean dfs(int[] nums, int i, Boolean[] memo) {
        if (i >= nums.length - 1) return true;
        if (memo[i] != null) return memo[i];
        for (int jump = 1; jump <= nums[i]; jump++) {
            if (dfs(nums, i + jump, memo)) {
                memo[i] = true;
                return true;
            }
        }
        memo[i] = false;
        return false;
    }
}

Scan left to right, maintaining the farthest index you can reach. If you ever stand on an index beyond the farthest reach, you are stuck. If the farthest reach covers the last index, you can make it.

Mental Model

Imagine walking along a number line where each position tells you the maximum distance you can jump forward. As you walk, keep a mental note of the farthest position you could possibly reach. If at any point your current position exceeds what you can reach, you are stranded on a zero-island and can never continue. If your farthest reach ever touches or passes the last index, you are done.

Algorithm Steps

1. Initialize farthest = 0 (the farthest index reachable so far).
2. Iterate i from 0 to n-1: a. If i > farthest, we cannot reach index i at all, so return false. b. Update farthest = max(farthest, i + nums[i]). c. If farthest >= n - 1, we can reach the end, return true.
3. After the loop, return true (we made it through every index).

Worked Walk-through

nums = [2, 3, 1, 1, 4], n = 5

Return true at step 2 because farthest (4) >= last index (4).

Another example: nums = [3, 2, 1, 0, 4], n = 5

We get stuck because index 3 has a 0 and we cannot jump past it.

Edge Cases

• Single element: nums = [0]. Already at the last index, return true.
• All zeros except first: nums = [0, ...]. If n > 1, index 0 has jump length 0, so farthest stays 0 and we cannot reach index 1. Return false.
• Large first jump: nums = [10, 0, 0, 0, 0]. farthest = 10 >= 4 on the first step, return true.

Complexity

• Time: O(n) -- single pass through the array.
• Space: O(1) -- only one variable farthest maintained.