Jump Game Problem in DSA Go - Build from Scratch

Jump Game Problem

📖 Scenario: You are playing a simple game where you jump through an array of platforms. Each platform has a number that tells you the maximum jump length from that platform. Your goal is to find out if you can reach the last platform starting from the first one.

🎯 Goal: Build a program that checks if you can jump from the first platform to the last platform using the jump lengths given in the array.

📋 What You'll Learn

Create an integer slice called jumps with the exact values: 2, 3, 1, 1, 4

Create an integer variable called maxReach and set it to 0

Use a for loop with variable i to iterate over the jumps slice and update maxReach to the maximum reachable index

Print true if the last platform is reachable, otherwise print false

💡 Why This Matters

🌍 Real World

This problem models situations like navigating through levels in a game or planning steps in a path with constraints.

💼 Career

Understanding how to analyze reachability and use loops with conditions is important in software development, especially in game development and algorithm design.

1

Create the jumps slice

Create an integer slice called jumps with these exact values: 2, 3, 1, 1, 4

DSA Go

# Create the jumps slice with values 2, 3, 1, 1, 4
# Your code here

Hint

Use jumps := []int{2, 3, 1, 1, 4} to create the slice.

2

Create maxReach variable

Create an integer variable called maxReach and set it to 0

DSA Go

package main

func main() {
    jumps := []int{2, 3, 1, 1, 4}
    // Create maxReach variable and set to 0
    // Your code here
}

Hint

Use maxReach := 0 to create the variable.

3

Calculate maximum reachable index

Use a for loop with variable i to iterate over the jumps slice. Inside the loop, update maxReach to the maximum of its current value and i + jumps[i]. Stop the loop if i is greater than maxReach.

DSA Go

package main

func main() {
    jumps := []int{2, 3, 1, 1, 4}
    maxReach := 0
    // Use for loop to update maxReach
    // Your code here
}

Hint

Use for i := 0; i < len(jumps); i++ to loop. Update maxReach inside the loop.

4

Print if last platform is reachable

Print true if maxReach is greater than or equal to len(jumps) - 1, otherwise print false

DSA Go

package main

import "fmt"

func main() {
    jumps := []int{2, 3, 1, 1, 4}
    maxReach := 0
    for i := 0; i  maxReach {
            break
        }
        if i+jumps[i] > maxReach {
            maxReach = i + jumps[i]
        }
    }
    // Print true if last platform reachable, else false
    // Your code here
}

Hint

Use fmt.Println(true) or fmt.Println(false) based on the condition.

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