Jump Game Problem in DSA Go

Mental Model

You have a list of numbers where each number tells you how far you can jump forward. The goal is to see if you can reach the end by jumping step by step.

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

stones: [2] -> [3] -> [1] -> [1] -> [4] -> null
          ↑start here

Dry Run Walkthrough

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

Goal: Check if we can jump from the first stone to the last stone following the jump rules.

Step 1: start at index 0 with max reachable index 0

index=0, maxReach=0

Why: We begin at the first stone and can only reach index 0 initially.

Step 2: from index 0, jump up to 2 steps ahead, update maxReach to 2

index=0, maxReach=2

Why: The first stone allows jumping 2 steps, so max reachable index is 2.

Step 3: move to index 1, update maxReach to max(2, 1+3)=4

index=1, maxReach=4

Why: From stone 1, we can jump 3 steps, extending maxReach to 4.

Step 4: move to index 2, maxReach remains 4

index=2, maxReach=4

Why: From stone 2, jump 1 step, maxReach stays 4 since 2+1=3 < 4.

Step 5: move to index 3, maxReach remains 4

index=3, maxReach=4

Why: From stone 3, jump 1 step, maxReach stays 4 since 3+1=4.

Step 6: index 4 is within maxReach 4, so we can reach the last stone

index=4, maxReach=4

Why: We can reach or pass the last stone, so answer is true.

Result:

stones: [2] -> [3] -> [1] -> [1] -> [4] -> null
Can reach end: true

Annotated Code

DSA Go

package main

import "fmt"

func canJump(nums []int) bool {
    maxReach := 0
    for i := 0; i < len(nums); i++ {
        if i > maxReach {
            return false
        }
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
    }
    return true
}

func main() {
    nums := []int{2, 3, 1, 1, 4}
    result := canJump(nums)
    fmt.Printf("stones: %v -> null\nCan reach end: %v\n", nums, result)
}

if i > maxReach { return false }

stop if current index is beyond max reachable index -- can't move forward

if i+nums[i] > maxReach { maxReach = i + nums[i] }

update max reachable index if current jump extends it

Output

stones: [2 3 1 1 4] -> null

Can reach end: true

Complexity Analysis

Time: O(n) because we scan the list once updating the farthest reachable index

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

vs Alternative: Compared to recursive or backtracking approaches that try all jumps (exponential time), this greedy method is much faster and simpler.

Edge Cases

empty list

returns true because we are already at the end

DSA Go

for i := 0; i < len(nums); i++ {

single element list [0]

returns true because start is the end

DSA Go

for i := 0; i < len(nums); i++ {

list with zero blocking progress [3,2,1,0,4]

returns false because cannot jump past zero at index 3

DSA Go

if i > maxReach { return false }

When to Use This Pattern

When you see a problem asking if you can reach the end by jumping steps defined by array values, use the greedy maxReach pattern to track how far you can go.

Common Mistakes

Mistake: Not checking if current index is beyond maxReach before updating maxReach
Fix: Add a condition to return false immediately if current index is unreachable

Mistake: Updating maxReach without comparing to current maxReach
Fix: Only update maxReach if current jump extends it beyond previous maxReach

Summary

Determines if you can reach the last index by jumping through the array using jump lengths at each position.

Use it when you need to check reachability in a sequence of jumps defined by array values.

Keep track of the farthest reachable index and stop early if you 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 within allowed steps

B. The maximum jump length you can make from any position

C. The minimum number of jumps 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 move from the first index to the last index by jumping forward within the allowed steps at each position.

2. Step 2: Identify the key question

   The key question is whether the last index is reachable, not how many jumps or maximum jump length.

3. Final Answer:

   If you can reach the last index starting from the first index by jumping within allowed steps -> Option A

4. Quick Check:

   Jump Game = Reach last index? [OK]

Hint: Focus on reachability, not jump count or max jump length [OK]

Common Mistakes:

• Confusing reachability with minimum jumps
• Thinking about maximum jump length instead
• Assuming sum of jumps matters

2. Which of the following Go code snippets correctly declares an integer slice representing jump lengths for the Jump Game?

easy

A. jumps := [2, 3, 1, 1, 4]

B. jumps := (2, 3, 1, 1, 4)

C. jumps := int{2, 3, 1, 1, 4}

D. jumps := []int{2, 3, 1, 1, 4}

Solution

1. Step 1: Recall Go slice declaration syntax

   In Go, slices are declared with []type and curly braces for values, e.g., []int{...}.

2. Step 2: Check each option

   Only jumps := []int{2, 3, 1, 1, 4} uses correct slice syntax. The others use array syntax, invalid int{}, or parentheses.

3. Final Answer:

   jumps := []int{2, 3, 1, 1, 4} -> Option D

4. Quick Check:

   Slice declaration = []int{values} [OK]

Hint: Use []int{...} to declare integer slices in Go [OK]

Common Mistakes:

• Using square brackets without type for slices
• Using parentheses instead of braces
• Confusing arrays and slices syntax

3. What is the output of the following Go code snippet for the Jump Game problem?

package main

import "fmt"

func canJump(nums []int) bool {
    maxReach := 0
    for i := 0; i < len(nums); i++ {
        if i > maxReach {
            return false
        }
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
    }
    return true
}

func main() {
    nums := []int{2, 3, 1, 1, 4}
    fmt.Println(canJump(nums))
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace maxReach updates

   Start 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 any index is unreachable

   All i ≤ maxReach, so no false return. Loop ends, returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   All indices reachable = true [OK]

Hint: Track max reachable index; if current index exceeds it, return false [OK]

Common Mistakes:

• Not updating maxReach correctly
• Returning false too early
• Ignoring the condition i > maxReach

4. Identify the bug in this Go function for the Jump Game problem and select the fix:

func canJump(nums []int) bool {
    maxReach := 0
    for i := 0; i <= len(nums); i++ {
        if i > maxReach {
            return false
        }
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
    }
    return true
}

medium

A. Remove the if condition checking i > maxReach

B. Initialize maxReach to 1 instead of 0

C. Change loop condition to i < len(nums)

D. Change return false to return true inside the loop

Solution

1. Step 1: Analyze loop boundary

   The loop runs with i <= len(nums), which causes index out of range error at i == len(nums).

2. Step 2: Fix loop condition

   Changing to i < len(nums) prevents out of range access and fixes the bug.

3. Final Answer:

   Change loop condition to i < len(nums) -> Option C

4. Quick Check:

   Loop index must be less than slice length [OK]

Hint: Use i < len(slice) to avoid index out of range errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring runtime panic from out of range
• Changing unrelated parts of code

5. Given the array nums := []int{3, 2, 1, 0, 4}, what is the result of applying the Jump Game algorithm to check if the last index is reachable?

hard

A. true

B. false

C. Runtime error due to zero jump

D. Depends on starting index

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 why last index is unreachable

   At index 3, jump length is 0, so maxReach does not increase. Index 4 is beyond maxReach, unreachable.

3. Final Answer:

   false -> Option B

4. Quick Check:

   Zero jump blocks progress = false [OK]

Hint: If maxReach stops before last index, return false [OK]

Common Mistakes:

• Assuming zero jump can be bypassed
• Ignoring unreachable last index
• Thinking runtime error occurs