LeetCode 55: Jump Game – Java Solution & Detailed Guide

Having trouble with LeetCode 55: Jump Game? This guide will walk you through a clean and efficient solution using a dynamic tracking strategy. Whether you’re gearing up for interviews or sharpening your algorithm skills, you’ll learn how to determine if it’s possible to reach the end of the array—step by step.

🧩 Problem Summary

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

Example:

Input: nums = [2, 3, 1, 1, 4]
Output: true

✅ You can jump from index 0 → 1 → 4.

🚀 Core Idea: Dynamic Reachability Tracking

The goal is to keep track of how far you can go at each index.

🔑 Key Steps:

1. Track Maximum Reachable Index using an array maxReach.
2. Iterate Through the Array and check:
   • Is the current index reachable?
   • If yes, update the farthest index we can reach.
   • If not, return false.

🧠 Example Walkthrough

Let’s walk through nums = [2, 3, 1, 1, 4]:

1. Index 0:
   • Initial maxReach[0] = 2. You can reach up to index 2.
2. Index 1:
   • Reachable, since maxReach[0] >= 1.
   • Update maxReach[1] = max(2, 1 + 3) = 4.
3. Index 2:
   • Reachable, maxReach[1] >= 2.
   • Update maxReach[2] = max(4, 2 + 1) = 4.
4. Index 3 & 4:
   • Already within reach. Since we can reach the end, return true.

💻 Java Code: Dynamic Approach

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n == 1) return true;

        int[] maxReach = new int[n];
        maxReach[0] = nums[0];

        for (int i = 1; i < n; i++) {
            if (maxReach[i - 1] < i) return false;  // Can't reach this index
            maxReach[i] = Math.max(maxReach[i - 1], i + nums[i]);
        }

        return maxReach[n - 1] >= n - 1;
    }
}

✅ Why It Works

• Time Complexity: O(n) – one pass through the array.
• Space Complexity: O(n) – due to the maxReach array.

It efficiently tracks the farthest reachable index at each step and ensures you never proceed to an unreachable index.

🧪 Edge Cases

1. Single Element – Return true, you’re already at the end.
2. Zeros in the Array – e.g., [3, 0, 0, 0] is valid if the first jump covers the distance.
3. Unreachable Index – e.g., [0, 2, 3] returns false.

⚡ Greedy Optimization (Space Efficient)

Instead of an array, use a single variable to track the farthest reachable index:

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

• Time: O(n)
• Space: O(1) – constant space.

This is the preferred approach in interviews due to its simplicity and efficiency.

🏁 Conclusion

The Jump Game problem is all about reachability and strategic thinking. Start with the dynamic approach to understand the logic, and level up to the greedy solution for optimal performance.

💡 Try This Next

Challenge yourself with [Jump Game II (LeetCode 45)] – where the goal is to find the minimum number of jumps needed to reach the end.

Keep coding and improving—every problem solved is a step closer to mastery. 🚀