55. Jump Game

At a Glance

Topic: greedy
Pattern: Greedy (reach farthest index)
Difficulty: Medium
Companies: Amazon, Google, Adobe, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 55

Problem (one-liner)

Given non-negative nums[index] max jump length from index, determine whether you can reach the last index starting at 0. Input: nums. Output: boolean.

Recognition Cues

“Can reach last index”
Greedy: track farthest index reachable as you sweep
No need to try all paths if farthest ≥ last

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DP / graph — mark reachable — O(n²) naive.
Greedy — maintain farthestReach — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func canJump(nums []int) bool {
	lastIndex := len(nums) - 1
	farthestReach := 0
	for index := 0; index <= farthestReach && index <= lastIndex; index++ {
		candidate := index + nums[index]
		if candidate > farthestReach {
			farthestReach = candidate
		}
		if farthestReach >= lastIndex {
			return true
		}
	}
	return farthestReach >= lastIndex
}

JavaScript

function canJump(nums) {
	const lastIndex = nums.length - 1;
	let farthestReach = 0;
	for (let index = 0; index <= farthestReach && index <= lastIndex; index++) {
		farthestReach = Math.max(farthestReach, index + nums[index]);
		if (farthestReach >= lastIndex) {
			return true;
		}
	}
	return farthestReach >= lastIndex;
}