Watch 10 video solutions for Jump Game, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by NeetCode has 290,114 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an 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.
Example 1:
Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 105Problem Overview: You receive an integer array where nums[i] represents the maximum jump length from index i. Starting at index 0, determine whether you can reach the last index. The challenge is deciding the best jumps without exploring every possible path.
Approach 1: Dynamic Programming (Top-Down / Bottom-Up) (Time: O(n²), Space: O(n))
This approach models the problem as reachability between indices. Create a boolean DP array where dp[i] indicates whether index i is reachable from the start. Initialize dp[0] = true, then iterate through the array and mark all positions reachable from each valid index. For index i, you attempt jumps to i + 1 through i + nums[i]. If any earlier reachable index can land on j, mark dp[j] as reachable. This brute-force style DP is straightforward and demonstrates the state transition clearly, but the nested iteration makes it O(n²) in the worst case. It’s mainly useful for understanding the problem before optimizing with a greedy observation. This method fits naturally when practicing dynamic programming patterns.
Approach 2: Greedy (Farthest Reach) (Time: O(n), Space: O(1))
The optimal solution tracks the farthest index you can reach while scanning the array once. Maintain a variable maxReach representing the farthest position reachable so far. As you iterate index i, check if i exceeds maxReach. If it does, that position is unreachable and the answer is false. Otherwise update maxReach = max(maxReach, i + nums[i]). This works because any earlier jump that reaches farther dominates shorter jumps, eliminating the need to explore all possibilities. The algorithm performs a single pass over the array, using constant extra memory, which makes it efficient for large inputs. The strategy is a classic greedy optimization where the locally optimal choice—tracking the farthest reachable index—guarantees the global solution.
Recommended for interviews: Interviewers expect the greedy O(n) solution. Starting with the DP idea shows you understand the reachability state and transition, but quickly identifying the farthest-reach observation demonstrates strong algorithmic intuition. The greedy scan is both simpler and faster, which is why it’s the standard production and interview solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | When learning the reachability state transition or building intuition before optimizing |
| Greedy (Farthest Reach) | O(n) | O(1) | Best general solution for interviews and large arrays |