Jump Game
MediumThe problem
You stand on index 0 of nums. Each nums[i] is the longest jump you can make from index i, and you may also jump any shorter distance. Return true if you can reach the last index, otherwise false.
- Example 1Input: nums = [2, 3, 1, 1, 4]Output: true
Jump 1 step to index 1, then 3 steps to the last index.
- Example 2Input: nums = [3, 2, 1, 0, 4]Output: false
Every path ends up on index 3, where nums[3] = 0 means you cannot move on.
- 1 ≤ len(nums) ≤ 100,000
- 0 ≤ nums[i] ≤ 100,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Do not simulate every jump — track only how far you can possibly reach.
The idea
Keep the farthest reachable index; if the current index is beyond it you are stuck; return true when farthest ≥ last.
Target: O(n) time, O(1) space
Go function shape
func canJump(nums []int) boolReference solution
Tested with go test. Try it yourself first, then compare.
// CanJump: can you reach the last index if nums[i] is the max jump length from i?
// Greedy: track the farthest index reachable so far. If we ever stand beyond it, we are stuck.
func CanJump(nums []int) bool {
farthest := 0
for i, jump := range nums {
if i > farthest { // an unreachable gap
return false
}
farthest = max(farthest, i+jump)
}
return true
}