Jump Game Problem in DSA Go - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check max jump from current index

↓

Can we reach or pass last index?

Yes→Return True

No↓

Move to next reachable index

↓

Repeat until no progress or end reached

↓

Return False if stuck

Start from the first position, check how far you can jump, move forward step by step until you reach or pass the last index or get stuck.

Execution Sample

DSA Go

package main

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

This code checks if you can jump from the start to the end of the array by updating the farthest reachable index.

Execution Table

Step	Operation	Current Index (i)	Max Reach	Condition i <= Max Reach	Action	Visual State
1	Start loop	0	0	0 <= 0 (True)	Check jump from index 0	[Index:0|Jump:2] -> MaxReach updated to 2
2	Update maxReach	0	2	-	maxReach = max(0, 0+2) = 2	[Index:0|Jump:2] MaxReach=2
3	Check if maxReach >= last index	0	2	-	2 >= 4? No	[MaxReach=2 < 4] Continue
4	Next iteration	1	2	1 <= 2 (True)	Check jump from index 1	[Index:1|Jump:3] MaxReach=2
5	Update maxReach	1	2	-	maxReach = max(2, 1+3) = 4	[Index:1|Jump:3] MaxReach updated to 4
6	Check if maxReach >= last index	1	4	-	4 >= 4? Yes	[MaxReach=4 >= 4] Return True
7	End	-	-	-	Reached or passed last index	[Success: Can reach end]

💡 Loop ends because maxReach reached or passed last index (4 >= 4)

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	Final
i	0	0	0	1	1	-
maxReach	0	0	2	2	4	4

Key Moments - 3 Insights

Why do we check if i <= maxReach in the loop condition?

Because if i becomes greater than maxReach, it means we cannot move forward anymore. The loop stops to avoid checking unreachable positions (see execution_table row 4).

Why update maxReach with max(maxReach, i + nums[i])?

We want to keep track of the farthest position reachable from any index visited so far. This ensures we don't miss longer jumps (see execution_table rows 2 and 5).

What happens if maxReach never reaches the last index?

The loop ends when i > maxReach, meaning we are stuck and cannot reach the end. The function returns false (not shown in this example but implied after loop).

Visual Quiz - 3 Questions

Look at the execution_table, what is maxReach after step 2?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Max Reach' column in row 2 of execution_table.

At which step does the condition maxReach >= last index become true?

A Step 3

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Check if maxReach >= last index' operation in execution_table.

If nums[1] was 1 instead of 3, what would maxReach be after step 5?

A 2

B 4

C 3

D 1

💡 Hint

Calculate maxReach = max(previous maxReach, i + nums[i]) with i=1 and nums[1]=1.

Concept Snapshot

Jump Game Problem:
- Start at index 0
- Track maxReach = farthest reachable index
- For each index i <= maxReach:
  Update maxReach = max(maxReach, i + nums[i])
- If maxReach >= last index, return true
- Else, return false

Full Transcript

The Jump Game problem asks if you can reach the last index of an array starting from the first index. Each element in the array represents the maximum jump length from that position. We start at index 0 and keep track of the farthest index we can reach, called maxReach. We loop through the array indices up to maxReach. At each index, we update maxReach if we can jump farther. If at any point maxReach reaches or passes the last index, we return true. If we get stuck and cannot move forward, we return false. This approach ensures we only check reachable positions and efficiently determine if the end is reachable.

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