Jump Game
Medium · Greedy · Array · Greedy · Dynamic Programming
Problem
You start at index 0. nums[i] is the furthest you may jump forward from index i. Return whether you can reach the last index.
Examples
Input: nums = [2,3,1,1,4] Output: True
Jump 1 to index 1, then 3 to the end.
Input: nums = [3,2,1,0,4] Output: False
Every route lands on the 0 at index 3 and stops.
Constraints
- 1 <= len(nums) <= 10^4
- 0 <= nums[i] <= 10^5
Approaches
- Backward dynamic programming — time O(n²), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
