Jump Game

1. Problem Description

Given an array nums of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents the maximum jump length at that position.

Determine whether you can reach the last index.

2. Approach

1. Approach 1
   • Brute-force DFS
   • Starting from index 0, try adding 0...nums[index] to the current index
   • Check whether the search can reach beyond the end of nums
2. Approach 2
   • Track the farthest reachable position

3. Implementation

3.1. Brute-Force DFS

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

func canJumpDFS(nums []int, index int) bool {
    if index >= len(nums) -1 {
        return true
    }
    steps := nums[index]
    if steps == 0 {
        return false
    }

    for i := steps; i > 0; i-- {
        if canJumpDFS(nums, index+i) {
            return true
        }
    }

    return false
}

3.2. Farthest Reach

func canJump2(nums []int) bool {
	// Initialize the farthest reachable position
	maxIndex := 0
	// index is the current position, step is the jump length at the current position
	index := 0
	step := 0
	for index, step = range nums {
		// If the current position is reachable and current position + jump length > farthest position
		nextMaxIndex := index + step
		if maxIndex >= index && nextMaxIndex > maxIndex {
			// Update the farthest reachable position
			maxIndex = nextMaxIndex
		}
	}

	return maxIndex >= index
}

4. References

• 55. Jump Game - LeetCode