Jump Game Problem in DSA Go - Time & Space Complexity

Time Complexity: Jump Game Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the Jump Game problem changes as the input size grows.

Specifically, how the number of steps to check jumps grows with the length of the input array.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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
}
    

This code checks if you can jump from the start to the end of the array, where each number shows the max jump length from that position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each position in the array once.
• How many times: The loop runs exactly once for each element, so n times if the array length is n.

How Execution Grows With Input

As the array gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows in a straight line with input size; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide if you can reach the end grows linearly with the number of positions.

Common Mistake

[X] Wrong: "Because we check jumps from each position, the time must be much bigger, like O(n²)."

[OK] Correct: The code only loops once through the array and updates the farthest reachable position without nested loops, so it stays linear.

Interview Connect

Understanding this linear time solution shows you can find efficient ways to solve problems that might seem complex at first.

Self-Check

"What if we changed the code to try all possible jumps from each position instead of just tracking the farthest reach? How would the time complexity change?"

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