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.
This approach involves maintaining a variable maxReach that stores the farthest index we can reach. We iterate through each index of the array and update maxReach. If at any index i, i is greater than maxReach, it means we cannot proceed further and thus return false. If we can iterate through the array successfully, return true.
In this C solution, we iterate over the array and update the maxReach variable, which tracks the furthest index we can reach. If at any point the current index is greater than maxReach, we return false because it means we are stuck. If we are able to iterate through the entire array, it means we can reach the last index, so we return true.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the array. We make a single pass through the array.
Space Complexity: O(1), as we use only constant extra space.
This approach uses a Dynamic Programming (DP) table to track whether you can reach each index. Initialize a boolean array dp of the same length as nums, set all elements to false except the first (set to true since you're already at the start). Iterate through the array, and for each index marked true, update reachable indices as true using the jump capability at that index. Finally, return the boolean value of the last index.
Here in C, we initialized a DP array with dp[0] set to true. For each true index i, the loop assesses how many indices beyond i are accessible and marks them as true, using the allowed jump.
At the end, we determine the reachability of the last index based on dp[numsSize-1].
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), due to potential nested loop invocations over n indices.
Space Complexity: O(n), for the DP array storing reachable status for elements.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the number of elements in the array. We make a single pass through the array. |
| Dynamic Programming Approach | Time Complexity: O(n^2), due to potential nested loop invocations over n indices. |
| 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 |
Jump Game - Greedy - Leetcode 55 • NeetCode • 290,114 views views
Watch 9 more video solutions →Practice Jump Game with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor