Jump Game - Solution & Explanation
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.
Approach 1: Greedy Approach
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.
Complexity
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.
Approach 2: Dynamic Programming Approach
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].
Complexity
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 3: Greedy
We use a variable mx to maintain the farthest index that can currently be reached, initially mx = 0.
We traverse the array from left to right. For each position i we traverse, if mx < i, it means that the current position cannot be reached, so we directly return false. Otherwise, the farthest position that we can reach by jumping from position i is i+nums[i], we use i+nums[i] to update the value of mx, that is, mx = max(mx, i + nums[i]).
At the end of the traversal, we directly return true.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| 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. |
| Greedy | — |
Detailed 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 |
Video Solution
Jump Game - Greedy - Leetcode 55 • NeetCode • 360,601 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Jump Game easy or hard?
Jump Game Python/Java solution
How to solve Jump Game in O(n)?
What is the best approach for Jump Game?
Is Jump Game asked at Google/Amazon/Meta?
What data structure is used in Jump Game?
What is the time complexity of Jump Game?
Ready to solve this problem?
Practice Jump Game with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor