Skip to content

Instantly share code, notes, and snippets.

@CollinShoop
Created January 19, 2022 22:33
Show Gist options
  • Save CollinShoop/22dc593432c0aa117636021f7678ac4a to your computer and use it in GitHub Desktop.
Save CollinShoop/22dc593432c0aa117636021f7678ac4a to your computer and use it in GitHub Desktop.
func canJump(nums []int) bool {
// can-jump cache
cache := map[int]bool{
0: true,
}
var canJump func(int) bool
canJump = func(to int) bool {
if canJumpTo, ok := cache[to]; ok {
return canJumpTo
}
for i := 0; i < to; i++ {
// check can jump from position "i" to "to"
if i + nums[i] >= to {
// if so, can you jump to "i"?
if ok := canJump(i); ok {
cache[to] = true
return true
}
}
}
cache[to] = false
return false
}
// work backwards from the end
return canJump(len(nums)-1)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment