← Back to DevBytes
Go August 05, 2026 9 min read

Solving Jump Game in Go: Step-by-Step Guide

Introduction to the Jump Game Problem

The Jump Game is one of the most popular algorithmic problems you'll encounter in coding interviews and competitive programming. It tests your understanding of greedy algorithms, dynamic programming, and array traversal. In this tutorial, we'll explore how to solve the Jump Game problem using Go, walking through multiple approaches from brute force to optimal solutions.

What Is the Jump Game?

Given an array of non-negative integers nums, you start at the first index. Each element in the array represents the maximum jump length you can take from that position. The goal is to determine whether you can reach the last index of the array.

For example, given [2, 3, 1, 1, 4], you can jump from index 0 to index 1, then from index 1 to the last index. However, with [3, 2, 1, 0, 4], you'll get stuck at index 3 because the maximum jump is 0.

Why It Matters

The Jump Game problem matters because it teaches fundamental concepts that apply to real-world scenarios:

Understanding the Problem Statement

Before writing any code, let's clearly define the problem. You are given an array nums where nums[i] represents the maximum number of steps you can jump forward from index i. You need to return true if you can reach the last index, otherwise false.

Key observations:

Approach 1: Recursive Solution (Brute Force)

The most intuitive approach is to try every possible jump from each position. At every index, you can jump between 1 and nums[i] steps, and you recursively check if any of those jumps leads to the last index.

package main

import "fmt"

func canJumpRecursive(nums []int, position int) bool {
    if position >= len(nums)-1 {
        return true
    }

    maxJump := nums[position]
    for jump := 1; jump <= maxJump; jump++ {
        if canJumpRecursive(nums, position+jump) {
            return true
        }
    }
    return false
}

func canJump(nums []int) bool {
    return canJumpRecursive(nums, 0)
}

func main() {
    fmt.Println(canJump([]int{2, 3, 1, 1, 4})) // true
    fmt.Println(canJump([]int{3, 2, 1, 0, 4})) // false
}

While this solution works, it has a time complexity of O(n^n) in the worst case, making it impractical for large inputs. Each position can branch into up to n recursive calls, leading to exponential growth.

Approach 2: Dynamic Programming with Memoization

We can improve the recursive solution by caching results. If we've already determined whether a position can reach the end, we don't need to recompute it. This technique is called memoization.

package main

import "fmt"

func canJumpMemo(nums []int, position int, memo []int) bool {
    if position >= len(nums)-1 {
        return true
    }

    if memo[position] != 0 {
        return memo[position] == 1
    }

    maxJump := nums[position]
    for jump := 1; jump <= maxJump; jump++ {
        if canJumpMemo(nums, position+jump, memo) {
            memo[position] = 1
            return true
        }
    }

    memo[position] = -1
    return false
}

func canJump(nums []int) bool {
    memo := make([]int, len(nums))
    return canJumpMemo(nums, 0, memo)
}

func main() {
    fmt.Println(canJump([]int{2, 3, 1, 1, 4})) // true
    fmt.Println(canJump([]int{3, 2, 1, 0, 4})) // false
}

Here, memo[i] stores 1 if position i can reach the end, -1 if it cannot, and 0 if unvisited. This reduces the time complexity to O(n^2) since each position is computed only once, and each computation iterates through at most n jumps.

Approach 3: Dynamic Programming (Bottom-Up)

Instead of recursing from the start, we can work backward from the last index. We mark the last position as reachable, then for each preceding index, we check if it can reach any already-reachable position.

package main

import "fmt"

func canJump(nums []int) bool {
    n := len(nums)
    if n == 0 {
        return false
    }

    reachable := make([]bool, n)
    reachable[n-1] = true

    for i := n - 2; i >= 0; i-- {
        maxJump := nums[i]
        for jump := 1; jump <= maxJump && i+jump < n; jump++ {
            if reachable[i+jump] {
                reachable[i] = true
                break
            }
        }
    }

    return reachable[0]
}

func main() {
    fmt.Println(canJump([]int{2, 3, 1, 1, 4})) // true
    fmt.Println(canJump([]int{3, 2, 1, 0, 4})) // false
}

This bottom-up approach eliminates recursion overhead and is easier to reason about. The time complexity remains O(n^2), but the space complexity is O(n) for the reachable array, with no recursion stack to worry about.

Approach 4: Greedy Algorithm (Optimal Solution)

The greedy approach is the most efficient way to solve the Jump Game. Instead of tracking which positions are reachable, we maintain a single variable representing the farthest index we can reach so far. As we iterate through the array, we update this maximum reach. If at any point our current index exceeds the maximum reach, we know we cannot proceed.

package main

import "fmt"

func canJump(nums []int) bool {
    maxReach := 0
    n := len(nums)

    for i := 0; i < n; i++ {
        if i > maxReach {
            return false
        }
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
        if maxReach >= n-1 {
            return true
        }
    }

    return maxReach >= n-1
}

func main() {
    fmt.Println(canJump([]int{2, 3, 1, 1, 4})) // true
    fmt.Println(canJump([]int{3, 2, 1, 0, 4})) // false
    fmt.Println(canJump([]int{0}))              // true
    fmt.Println(canJump([]int{0, 1}))           // false
}

This solution runs in O(n) time with O(1) space, making it optimal. The key insight is that we don't need to know exactly how we reach the end—only whether it's possible. By tracking the farthest reachable index, we make a single pass through the array.

How the Greedy Approach Works Step by Step

Let's trace through [2, 3, 1, 1, 4]:

Now let's trace through [3, 2, 1, 0, 4]:

Variant: Jump Game II (Minimum Jumps)

A common follow-up asks for the minimum number of jumps needed to reach the last index. This variant uses a similar greedy approach but tracks jumps and the current range of reachable positions.

package main

import "fmt"

func jump(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }

    jumps := 0
    currentEnd := 0
    farthest := 0

    for i := 0; i < n-1; i++ {
        if i+nums[i] > farthest {
            farthest = i + nums[i]
        }

        if i == currentEnd {
            jumps++
            currentEnd = farthest

            if currentEnd >= n-1 {
                break
            }
        }
    }

    return jumps
}

func main() {
    fmt.Println(jump([]int{2, 3, 1, 1, 4})) // 2
    fmt.Println(jump([]int{2, 3, 0, 1, 4})) // 2
}

The idea is to divide the array into jump ranges. currentEnd marks the boundary of the current jump, and farthest tracks the maximum reach within that range. When we hit currentEnd, we must take a jump, and we set the new boundary to farthest.

Best Practices for Solving Jump Game Problems

Start with the Greedy Approach

Whenever you encounter a reachability problem involving maximum jumps or steps, consider a greedy solution first. Tracking the farthest reachable index is a powerful pattern that often leads to O(n) solutions.

Handle Edge Cases Early

Always consider edge cases such as empty arrays, single-element arrays, arrays starting with zero, and arrays where the first element is large enough to reach the end in one jump. Handling these upfront prevents bugs and improves code clarity.

func canJump(nums []int) bool {
    n := len(nums)
    if n == 0 {
        return false
    }
    if n == 1 {
        return true
    }
    if nums[0] == 0 {
        return false
    }
    // ... rest of the logic
}

Use Descriptive Variable Names

Names like maxReach, farthest, and currentEnd make your code self-documenting. Avoid single-letter variables except for loop counters, as clarity matters more than brevity in interview and production settings.

Test with Diverse Inputs

Create a comprehensive test suite covering various scenarios:

package main

import "testing"

func TestCanJump(t *testing.T) {
    tests := []struct {
        nums     []int
        expected bool
    }{
        {[]int{2, 3, 1, 1, 4}, true},
        {[]int{3, 2, 1, 0, 4}, false},
        {[]int{0}, true},
        {[]int{0, 1}, false},
        {[]int{1, 0, 1, 0}, false},
        {[]int{5, 0, 0, 0, 0, 0}, true},
        {[]int{1, 1, 1, 1, 1}, true},
        {[]int{1, 0, 0, 0, 1}, false},
    }

    for _, tt := range tests {
        result := canJump(tt.nums)
        if result != tt.expected {
            t.Errorf("canJump(%v) = %v, expected %v", tt.nums, result, tt.expected)
        }
    }
}

Avoid Unnecessary Memory Allocation

The greedy approach uses O(1) space, which is ideal. If you find yourself allocating arrays for tracking state, reconsider whether a simpler approach exists. Go's value semantics mean slice allocations have real costs, so prefer in-place tracking variables when possible.

Common Pitfalls to Avoid

Performance Comparison

Here's a summary of the time and space complexities for each approach we covered:

For any input larger than a few dozen elements, only the greedy approach performs well. The recursive solution will time out, and even the DP solutions may struggle with very large inputs.

Conclusion

The Jump Game problem is an excellent exercise in algorithmic thinking that progresses naturally from brute force to an elegant greedy solution. By starting with recursion, adding memoization, converting to bottom-up dynamic programming, and finally arriving at the greedy approach, you develop a deep understanding of how optimization works at each level. The key takeaway is that tracking the farthest reachable index in a single pass gives you an O(n) solution with O(1) space—the optimal answer for this problem. Master this pattern, and you'll be well-equipped to tackle similar reachability and greedy problems in Go, whether in interviews or real-world applications.

— Ad —

Google AdSense will appear here after approval

← Back to all articles