package main

func canJumpIter(nums []int, visited map[int]bool, pos int) bool {
	if visited[pos] {
		return false
	}
	visited[pos] = true
	if pos+nums[pos] >= len(nums)-1 {
		return true
	}
	if nums[pos] == 0 {
		return false
	}
	for i := 1; i <= nums[pos]; i++ {
		if canJumpIter(nums, visited, pos+i) {
			return true
		}
	}
	return false
}

// TLE
func canJumpOld(nums []int) bool {
	return canJumpIter(nums, map[int]bool{}, 0)
}

func canJump(nums []int) bool {
	// leap: the longest distance of jumping at idx 'i'
	for i, leap := 0, 0; i < len(nums); i, leap = i+1, leap-1 {
		if leap < 0 {
			return false
		}
		if nums[i] > leap {
			leap = nums[i]
		}
	}
	return true
}

/* func main() {
	a1 := []int{2, 3, 1, 1, 4}
	a2 := []int{3, 2, 1, 0, 4}
	a3 := []int{0}
	fmt.Println(canJump(a1))
	fmt.Println(canJump(a2))
	fmt.Println(canJump(a3))
} */