← Back to Index

📚 Jump Game – Java Cheat Sheet

📌 What Is It?

The Jump Game problem involves determining whether you can reach the last index of an array starting from the first index. Each element in the array represents the maximum jump length at that position.

🧱 Pattern Template

Greedy Algorithm

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;

        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false; // If current index is unreachable
            }
            maxReach = Math.max(maxReach, i + nums[i]); // Update max reachable index
        }

        return true; // If we can reach or exceed the last index
    }
}

▶️ View Animation

📊 Time Complexity

• Time Complexity: O(N), where N is the size of the input array. We iterate through the array once.
• Space Complexity: O(1), as we use only a constant amount of extra space.

✅ Use Cases

• Determining if you can reach the end of an array with given jump lengths.
• Solving problems involving reachability in linear structures.

📘 Common LeetCode Problems

• 55. Jump Game [Medium] Greedy
• 45. Jump Game II [Hard] Greedy

🧪 Example

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

Explanation:
- Start at index 0 with value 2. You can jump to index 1 or 2.
- From index 1 with value 3, you can jump to index 4 (last index).

💡 Pro Tips

• Keep track of the maximum reachable index as you iterate through the array.
• If the current index exceeds the maximum reachable index, return false.
• Edge case: If the array has only one element, return true.