Jump Game (LC 55)

Pattern: Greedy / “reachability” DP
Difficulty: Medium
Key Concept: Track the farthest index reachable from the start; if you ever reach an index beyond current reach, fail; if reach ≥ last index, succeed.

Problem Statement

You are given an integer array nums. You are initially at index 0. Each element nums[i] represents your maximum jump length from position i.

Return true if you can reach the last index, otherwise false.

Input: nums (non-empty, nums[i] >= 0).
Output: boolean.

Examples:

• [2,3,1,1,4] → true.
• [3,2,1,0,4] → false (stuck at 0).

---

1. Algorithm & Pseudocode

Brute force

1. DFS/BFS from index 0: from i, try every step 1..nums[i] to i+k.
2. Memoize index i as reachable or not—still can be heavy for large branching.
3. Naive without pruning revisits many states.

Pseudocode (DFS + memo):

memo[i] = UNKNOWN / GOOD / BAD
function can(i):
    if i == n-1: return true
    mark BAD if dead end
    for step in 1..nums[i]:
        if can(i + step): return true
    return false

Optimal (greedy)

1. Maintain reach = farthest index you can get to so far.
2. For each i from 0 to n-1:
   • If i > reach, you cannot stand at i → return false.
   • reach = max(reach, i + nums[i]).
   • If reach >= n - 1, return true.
3. If loop completes, return reach >= n - 1.

Pseudocode:

reach = 0
for i from 0 to n-1:
    if i > reach: return false
    reach = max(reach, i + nums[i])
return true

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why greedy is safe: Only reachability matters, not which path you took. If you can reach index i, every index < i was passable in some order; extending reach from i captures all jumps you could defer.

Why i > reach fails: You cannot land on i without crossing a gap—reach is the maximum “frontier.”

Relation to DP: dp[i] = reachable can be computed left-to-right; greedy compresses to one number reach.

---

3. The Dry Run

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

i	nums[i]	i > reach?	reach before	reach after max(reach, i+nums[i])
0	2	no	0	max(0,2)=2
1	3	no	2	max(2,4)=4
2	1	no	4	4
3	1	no	4	4
4	4	no	4	max(4,8)=8

reach >= n-1 (4) → true.

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

i	…	note
0	reach=3	ok
…	at i=4	i=4 > reach=3 → false

---

4. Java Solution

Brute Force

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

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

Time: O(n^2) worst with memo (each cell once, inner loop). Space: O(n).

Optimal

public class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > reach) {
                return false;
            }
            reach = Math.max(reach, i + nums[i]);
            if (reach >= n - 1) {
                return true;
            }
        }
        return true;
    }
}

Time: O(n). Space: O(1).

---

5. The “Java vs. Others” Edge

• Boolean[] memo allows null as “unknown”; boolean[] needs a separate visited bit or -1 in byte.
• Greedy uses primitive int—fast and allocation-free.
• Early exit when reach >= n-1 saves iterations in long arrays.

---

6. Complexity Summary

Approach	Time	Space	Notes
DFS (no memo)	Exponential	O(n)	Bad for large nums[i]
DFS + memo	O(n^2) worst	O(n)	Still quadratic edges
Greedy reach	O(n)	O(1)	Standard “Blind 75” answer