🏃

Greedy Reach — Jump Game I & II

Track maxReach — the farthest index reachable so far. For Jump Game II, also track currEnd (boundary of current jump) and increment jumps each time i crosses it. One pass, O(n).

🏃 Max Reach Tracking ⚡ O(n) One Pass 🎯 Jump Boundary Time O(n) Space O(1)

📋 When to Use

Can you reach end? (Jump Game I) — track maxReach; if ever i > maxReach, return false
Minimum jumps to end? (Jump Game II) — track currEnd (current jump boundary) and maxReach; when i == currEnd, you MUST jump → jumps++, currEnd = maxReach
Loop only up to n-2 (don't need to jump from last index)
Key insight: you never need to track WHICH jump — only WHERE the current boundary is

💡 Both problems use a single left-to-right scan. The greedy choice is: at every index, maximize how far you can reach. You jump only when forced (when you hit the current boundary).

⚡ Complexity

Time

O(n)

Space

O(1)

Single left-to-right scan — O(n) time.
Just three variables: maxReach, currEnd, jumps — O(1) space.
Compare: DP approach is O(n²) — greedy is optimal.
No array, no stack, no extra data structures needed.

Problem Given nums = [2,3,1,1,4] where each element is the maximum jump length from that index, determine if you can reach the last index (LC #55). Then find the minimum number of jumps needed to reach it (LC #45). Greedily track the farthest reachable index — no need to simulate every path.
Input: nums = [2, 3, 1, 1, 4] · Answer: #55 → true · #45 → 2 jumps (path: 0 → index 1 → index 4)

Step 0 / 5

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

active i

within maxReach

currEnd boundary

reached end

🏃 Jump Game I: Can you reach the end? Track maxReach — the farthest index reachable. Scan left to right, updating maxReach at each index.

int maxReach = 0;

🧩 Pattern Skeleton Java 8

// ─── Jump Game I — can you reach end? ────────────────
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;           // blocked: can't reach i
    maxReach = Math.max(maxReach, i + nums[i]);
}
return true;  // maxReach >= last index

// ─── Jump Game II — minimum jumps ────────────────────
int jumps = 0, currEnd = 0, maxReach = 0;
for (int i = 0; i < nums.length - 1; i++) {  // don't jump FROM last
    maxReach = Math.max(maxReach, i + nums[i]);
    if (i == currEnd) {                       // boundary reached: must jump
        jumps++;
        currEnd = maxReach;
    }
}
return jumps;

🎯 Practice Problems

#55 Jump Game 🏃 maxReach greedy Medium #45 Jump Game II 🎯 currEnd boundary Medium #1306 Jump Game III 🔍 can reach zero — BFS/DFS Medium #1345 Jump Game IV ⚡ same-value jumps — BFS Hard #134 Gas Station 🔄 greedy circular reach Medium #860 Lemonade Change 💰 greedy simulation Easy