DSA problem
Jump Game
You are given a 0-indexed integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.
A naive approach is dynamic programming or DFS: try every possible jump from every position and remember which indices are reachable. That works but spends O(n^2) time in the worst case, because positions near the start can branch into many futures.
The greedy reformulation flips the question. Rather than asking "can I reach index n-1 from here?", ask "what is the farthest index reachable so far?" Walk left-to-right, maintaining a single variable maxReach. At each index i, if i > maxReach the array has a gap we cannot cross — return false immediately. Otherwise update maxReach = max(maxReach, i + nums[i]) and continue. If you finish the loop without failing, the last index is reachable.
This is correct because reachability is monotone: if index i is reachable and nums[i] >= k, then every index from i+1 to i+k is also reachable. So the union of reachable indices is always a contiguous prefix [0, maxReach], and the greedy update tracks its right endpoint exactly. The algorithm is a single linear pass — O(n) time, O(1) space — and provably optimal.
Examples
nums = [2,3,1,1,4]truenums = [3,2,1,0,4]falsenums = [0]trueConstraints
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.