Greedy Algorithms8 sections · 316 units
Open in Course

Jump Game - The Idea

Track furthest reachable

Track the furthest index you can reach. At each position i, update furthest = max(furthest, i + nums[i]).

If you ever have i > furthest, you are stuck and cannot proceed.

If furthest >= n1n-1, you can reach the end. It works because reaching position i means you had some path there. What matters is how far you can go from any reachable position. Common bug: checking furthest before updating it, which misses the current position's contribution.