Jump Game - Greedy - Leetcode 55
Jump Game - Video Solution
Watch 10 video solutions for Jump Game, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by NeetCode has 360,601 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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] <= 105
Approach Overview
Problem Overview: You are given an 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 how to choose jumps so you never get stuck at a position that cannot progress further.
Approach 1: Dynamic Programming (O(n^2) time, O(n) space)
This approach treats the problem as a reachability question. Create a DP array where dp[i] indicates whether index i can reach the last position. Start from the end of the array and work backward. For each index i, iterate through all possible jumps from 1 to nums[i] and check if any reachable index already leads to the end. If such a position exists, mark dp[i] as true. This method clearly models the state transition but performs many repeated checks, leading to O(n^2) time in the worst case. It’s useful for understanding the state relationship in dynamic programming problems where future reachability depends on previously computed states.
Approach 2: Greedy (O(n) time, O(1) space)
The greedy insight removes the need to track every reachable state. Instead, maintain the farthest index you can reach while scanning the array from left to right. At each position i, check if it is still reachable (i.e., i ≤ farthest). If it is, update farthest = max(farthest, i + nums[i]). If at any point the current index exceeds farthest, the path is blocked and reaching the end becomes impossible. If farthest reaches or exceeds the last index during iteration, the answer is true. This works because the only thing that matters is the maximum reachable boundary so far, not the specific path taken. The solution runs in linear time and constant space, making it the optimal strategy for this array traversal problem and a classic example of a greedy algorithm.
Recommended for interviews: Interviewers typically expect the greedy solution because it reduces the problem to a single pass with O(n) time and O(1) space. Explaining the dynamic programming approach first can show you understand the reachability state transition, but recognizing that only the farthest reachable index matters demonstrates stronger algorithmic intuition and optimization skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | Useful for understanding reachability states and transitions in DP problems |
| Greedy | O(n) | O(1) | Best for interviews and production; tracks farthest reachable index in one pass |