LeetCode Study Note | Problem 55: Jump Game

🧠 Problem Overview

You’re given an integer array nums, where each element represents the maximum jump length from that position. Starting at index 0, determine if you can reach the last index.

Example 1

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

Output: true

Explanation: 0 → 1 → 4

Example 2

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

Output: false

Explanation: Stuck at index 3, can’t jump to 4.

⚙️ Method 1: Greedy

🧩 Intuition

We only care about the farthest index we can reach at each step.

If at any index i, we find that i is beyond the farthest reachable index so far, it means we’re stuck and cannot proceed.

So we maintain a variable rightmost — the farthest index we can reach as we iterate through the array.

For each index i:

• If i <= rightmost, we can reach it.

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

• If rightmost reaches or exceeds the last index, return True.

Otherwise, after the loop, if rightmost < last index, return False.

🔍 Walkthrough Examples

✅ Example 1: 

[2, 3, 1, 1, 4]

1. Start at index 0 → rightmost = max(0, 0 + 2) = 2

2. Index 1 is within reach → rightmost = max(2, 1 + 3) = 4

3. 4 ≥ last index → return True

❌ Example 2: 

[3, 2, 1, 0, 4]

1. Start at index 0 → rightmost = 3

2. Index 1, 2, 3 are all ≤ 3, but no further jump improves rightmost

3. Index 4 > rightmost, unreachable → return False

🧑‍💻 Code (Java)

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

⏱️ Complexity Analysis

• Time Complexity: O(n) — We scan the array once.

• Space Complexity: O(1) — No extra space used.