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.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

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

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;
}

Walkthrough

nums = [2,3,1,1,4]

Reach last without scanning further.

Invariant: farthestReach is max index reachable using positions 0..index.

Edge Cases

• Single element → true
• First element 0 and length > 1 → false

Pitfalls

• Off-by-one on last index
• Confusing with Jump Game II minimum jumps

Similar Problems

• 45. Jump Game II — minimum jumps to end.
• 056. Merge Intervals — sweeping / ordering tricks on segments.
• 134. Gas Station — circular greedy feasibility.

Variants

• Minimum removals to reach end → different problem.

Mind-Map Tags

#greedy #reachability #farthest-index #medium