Solving the LeetCode "Jump Game" Problem in Go

Difficulty: Medium | Tags: Array, Dynamic Programming, Greedy

Introduction

The "Jump Game" problem requires determining whether it's possible to reach the last index of an array, where each element represents the maximum jump length from that position. This problem tests understanding of greedy algorithms and dynamic programming.

Problem Analysis

Given an array of non-negative integers, we start at the first index and can jump up to the value at the current index. The goal is to check if the last index is reachable. For example, in [2,3,1,1,4], we can jump from index 0 to 1, then to the last index. However, in [3,2,1,0,4], we get stuck at index 3.

Solution Approach

A greedy approach works efficiently here. We track the farthest reachable index as we iterate through the array. If at any point the current index exceeds the farthest reachable index, we return false. Otherwise, if we reach or surpass the last index, we return true.

Go Implementation

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]
        }
        if maxReach >= len(nums)-1 {
            return true
        }
    }
    return false
}

Complexity Analysis

The algorithm runs in O(n) time, where n is the length of the array, as we traverse the array once. The space complexity is O(1) since we only use a few variables.

Testing and Examples

Test cases include:
1. [2,3,1,1,4] → true
2. [3,2,1,0,4] → false
3. [0] → true (single element)
4. [1,0,1,0] → false (stuck at index 1)

Best Practices and Tips

Key takeaways:
- Use a greedy approach for optimal performance.
- Always check edge cases like single-element arrays.
- Track the farthest reachable index dynamically.