LeetCode Study Note | Problem 45: Jump Game II

🧩 Problem Summary

You are given an integer array nums where each element represents your maximum jump length at that position. Your goal is to return the minimum number of jumps to reach the last index (starting from index 0).

You can always assume that it is possible to reach the end.

🎯 Key Insight

This is a greedy algorithm problem. The trick is to:

• Always keep track of the current jump range (end)

• Update the farthest reachable position (maxPosition) at each step

• Only increase the step count when we reach the end of the current jump range

🧠 Greedy Strategy

“Only jump when necessary, but always jump to the farthest possible range.”

At every position i:

• Update maxPosition = max(maxPosition, i + nums[i])

• If i == end:

  • This means we’ve finished the current jump range

  • So we steps++ and start a new jump range up to maxPosition

💻 Java Code

class Solution {
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;

        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

🔍 Example Trace

Input: [2,3,1,1,4]

Jump Path:

• Start at index 0, can jump to [1, 2], among which index 1 can reach index 4

• First jump: 0 → 1

• Second jump: 1 → 4

Result: 2 jumps

🔄 Comparison with Problem 55

🧠 Why Greedy Works

Greedy works here because:

• We only jump when we must

• We always choose the jump that gives us the farthest reach

• This ensures minimal jumps and avoids unnecessary hops

🛠️ Complexity

• Time: O(n) (each index is visited once)

• Space: O(1) (no extra memory)

🧸 Takeaways

• Maintain a greedy frontier of how far we can go each time

• Don’t jump too early; only jump when necessary

• Greedy is perfect when local optimal → global optimal