Jump Game Problem in DSA Java

Mental Model

You can jump forward from each position by a number of steps given in an array. The goal is to see if you can reach the last position starting from the first.

Analogy: Imagine standing on stepping stones across a river. Each stone has a number telling you how far you can jump forward. You want to know if you can reach the last stone without falling in the water.

Index: 0   1   2   3   4
Array: [2] [3] [1] [1] [4]
Start ↑

Dry Run Walkthrough

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

Goal: Determine if you can jump from the first index to the last index

Step 1: Start at index 0 with jump length 2, update max reachable index to 2

Current index: 0, max reachable index: 2

Why: From index 0, you can jump up to index 2, so max reachable is 2

Step 2: Move to index 1 with jump length 3, update max reachable index to 4

Current index: 1, max reachable index: 4

Why: From index 1, you can jump up to index 4, which is farther than previous max 2

Step 3: Move to index 2 with jump length 1, max reachable remains 4

Current index: 2, max reachable index: 4

Why: From index 2, max reachable is index 3, which is less than current max 4

Step 4: Move to index 3 with jump length 1, max reachable remains 4

Current index: 3, max reachable index: 4

Why: From index 3, max reachable is index 4, equal to current max

Step 5: Since max reachable index 4 is at or beyond last index 4, return true

Reached or passed last index

Why: We can reach the last index from the jumps

Result:

Final max reachable index: 4 -> can reach last index (4) -> true

Annotated Code

DSA Java

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false; // can't reach this position
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true; // can reach or pass last index
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(canJump(nums));
    }
}

if (i > maxReach) { return false; }

If current index is beyond max reachable, we cannot proceed

maxReach = Math.max(maxReach, i + nums[i]);

Update max reachable index based on current jump

if (maxReach >= nums.length - 1) { return true; }

If max reachable covers last index, we can reach the end

Output

true

Complexity Analysis

Time: O(n) because we scan the array once updating the max reachable index

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to a recursive or backtracking approach which can be exponential, this greedy method is much faster and uses less memory

Edge Cases

Empty array

Returns false since the loop does not execute

DSA Java

for (int i = 0; i < nums.length; i++) {

Single element array [0]

Returns true because start is also the last index

DSA Java

if (maxReach >= nums.length - 1) { return true; }

Array with zero blocking progress, e.g. [3,2,1,0,4]

Returns false because cannot jump past zero at index 3

DSA Java

if (i > maxReach) { return false; }

When to Use This Pattern

When you see a problem asking if you can reach the end by jumping variable steps, use the greedy max reachable index pattern to efficiently check reachability.

Common Mistakes

Mistake: Not checking if current index is beyond max reachable, leading to incorrect true result
Fix: Add a condition to return false immediately if current index is greater than max reachable

Mistake: Updating max reachable incorrectly by not using max function
Fix: Use max to keep the farthest reachable index so far

Summary

Determines if you can jump from start to end of array using jump lengths at each index

Use when you need to check reachability in a jump or step-based problem

Keep track of the farthest index you can reach and verify you never get stuck

Practice

1. What does the Jump Game problem ask you to determine given an array of non-negative integers?

easy

A. If you can reach the last index starting from the first index by jumping according to array values

B. The maximum jump length you can make from the first index

C. The minimum number of jumps needed to reach the last index

D. The sum of all jump lengths in the array

Solution

1. Step 1: Understand the problem statement

   The Jump Game problem asks if you can start at the first index and reach the last index by jumping forward using the values at each index as maximum jump lengths.

2. Step 2: Identify the goal

   The goal is to check if reaching the last index is possible, not the number of jumps or sums.

3. Final Answer:

   If you can reach the last index starting from the first index by jumping according to array values -> Option A

4. Quick Check:

   Jump Game = Reach last index? [OK]

Hint: Jump Game checks reachability, not jump count or sums [OK]

Common Mistakes:

• Confusing reachability with minimum jumps
• Thinking problem asks for maximum jump length
• Assuming sum of jumps is required

2. Which of the following Java method signatures correctly represents a function to solve the Jump Game problem?

easy

A. public void canJump(int[] nums)

B. public int canJump(int[] nums)

C. public boolean canJump(int[] nums)

D. public String canJump(int[] nums)

Solution

1. Step 1: Determine the return type

   The Jump Game problem returns true or false depending on whether the last index is reachable, so the return type should be boolean.

2. Step 2: Check method signature correctness

   The method should accept an integer array and return a boolean, matching public boolean canJump(int[] nums).

3. Final Answer:

   public boolean canJump(int[] nums) -> Option C

4. Quick Check:

   Return type boolean for reachability [OK]

Hint: Jump Game method returns boolean for reachability [OK]

Common Mistakes:

• Using int return type instead of boolean
• Using void return type without returning result
• Returning String instead of boolean

3. What is the output of the following Java code snippet?

int[] nums = {2, 3, 1, 1, 4};
System.out.println(canJump(nums));

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

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Trace the loop and maxReach updates

   Start with maxReach=0. At i=0, maxReach=max(0,0+2)=2. i=1 ≤ 2, maxReach=max(2,1+3)=4. i=2 ≤ 4, maxReach=max(4,2+1)=4. i=3 ≤ 4, maxReach=max(4,3+1)=4. i=4 ≤ 4, maxReach=max(4,4+4)=8.

2. Step 2: Check if loop completes without returning false

   Since i never exceeds maxReach, loop completes and returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   maxReach covers all indices, so true [OK]

Hint: Track maxReach; if index > maxReach, return false [OK]

Common Mistakes:

• Stopping early without updating maxReach
• Confusing maxReach with current index
• Ignoring the condition i > maxReach

4. Identify the bug in the following Java code for the Jump Game problem:

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

medium

A. The loop condition should be 'i < nums.length' instead of 'i <= nums.length' to avoid ArrayIndexOutOfBoundsException.

B. The maxReach update is incorrect; it should subtract 1 from i + nums[i].

C. The return type should be int, not boolean.

D. The method should return false at the end instead of true.

Solution

1. Step 1: Analyze the loop condition

   The loop runs from i=0 to i <= nums.length, which means it tries to access nums[nums.length], causing an ArrayIndexOutOfBoundsException.

2. Step 2: Correct the loop condition

   The loop should run while i < nums.length to stay within array bounds.

3. Final Answer:

   The loop condition should be 'i < nums.length' instead of 'i <= nums.length' to avoid ArrayIndexOutOfBoundsException. -> Option A

4. Quick Check:

   Array index must be less than length [OK]

Hint: Use i < nums.length to avoid array index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Incorrect maxReach calculation
• Wrong return type for method

5. Given the array nums = {3, 2, 1, 0, 4}, why does the standard greedy Jump Game algorithm return false, and what does this imply about the array?

hard

A. Because the array length is too short to jump anywhere

B. Because index 3 has zero jump length blocking progress, making the last index unreachable

C. Because the first element is too large, causing an overflow error

D. Because the algorithm only works for arrays with all positive numbers

Solution

1. Step 1: Trace maxReach through the array

   Start maxReach=0. i=0: maxReach=max(0,0+3)=3. i=1 ≤ 3: maxReach=max(3,1+2)=3. i=2 ≤ 3: maxReach=max(3,2+1)=3. i=3 ≤ 3: maxReach=max(3,3+0)=3. i=4 > 3, so return false.

2. Step 2: Understand the implication

   Index 3 has zero jump length, blocking further progress, so the last index (4) is unreachable.

3. Final Answer:

   Because index 3 has zero jump length blocking progress, making the last index unreachable -> Option B

4. Quick Check:

   Zero jump blocks path, so false [OK]

Hint: Zero jump at blocking index means last index unreachable [OK]

Common Mistakes:

• Assuming large first element guarantees success
• Ignoring zero jump blocking
• Thinking algorithm fails on zeros always