55. Jump Game
You stand on index 0 of an integer array nums, where each value is a jump allowance: from index i you may hop forward to any index between i + 1 and i + nums[i], inclusive. A 0 allows no movement at all.
Your function receives nums and returns a boolean: true if some sequence of hops can land you on the last index, false if every route eventually strands you on a zero you cannot clear.
Note that an allowance is a maximum, not a mandate — you may always jump shorter than the value permits, and an array of length 1 counts as already standing on the goal.
Example 1:
Input: nums = [2, 3, 1, 1, 4]
Output: true
Explanation: Hop from index 0 to index 1 (allowance 2 permits it), then the allowance 3 reaches index 4, the last index.
Example 2:
Input: nums = [3, 2, 1, 0, 4]
Output: false
Explanation: However you play it, every route funnels into index 3, whose allowance 0 permits no further move — index 4 is unreachable.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁵
Hints:
You do not need the path, only reachability — so track the single most useful fact: the farthest index any explored position can reach.
Sweep left to right maintaining farthest = max(farthest, i + nums[i]). If the loop ever arrives at an index i > farthest, you are standing past everything reachable — the answer is false. Reach the end (or farthest >= last index) and it is true.
Equivalent greedy in reverse: walk from the right keeping the leftmost index known to reach the goal; index i qualifies when i + nums[i] reaches that marker. The answer is whether the marker ends at 0.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 3, 1, 1, 4]
Expected output: true