Jump Game solution and explanation
Google
TCS
9 more videos on this problem
Jump Game - Greedy - Leetcode 55NeetCode · 16:28 · 360K views
L4. Jump Game - I | Greedy Algorithm Playlisttake U forward · 10:53 · 265K views
LeetCode 55. Jump Game (Algorithm Explained)Nick White · 10:06 · 81K views
Jump Game (LeetCode 55) | Full solution with animations and visuals | Greedy AlgorithmsNikhil Lohia · 18:35 · 60K views
Jump Game - Leetcode 55 - Dynamic Programming (Python)Greg Hogg · 8:42 · 21K views
Jump Game | Leetcode 55 | Top 150 interview question seriesTechnosage · 8:22 · 9K views
Jump Game - LeetCode 55 - JavaScriptAlgoJS · 5:11 · 2K views
Jump Game - LeetCode 55 - Coding Interview QuestionsOne Code Man · 7:12 · 2K views
[Java] Leetcode 55. Jump Game [DP Decision Making #3]Eric Programming · 13:15 · 2K views
Jump Game | LeetCode 55 (Medium)Destination FAANG · 19:34 · 1K views
The problem
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.
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i, num in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + num)
if max_reach >= len(nums) - 1:
return True
return Falseclass Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return false;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxReach = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > maxReach) return false;
maxReach = max(maxReach, i + nums[i]);
if (maxReach >= nums.size() - 1) return true;
}
return false;
}
};var canJump = function(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return false;
};#include <stdbool.h>
bool canJump(int* nums, int numsSize) {
int maxReach = 0;
for (int i = 0; i < numsSize; i++) {
if (i > maxReach) return false;
if (i + nums[i] > maxReach) maxReach = i + nums[i];
if (maxReach >= numsSize - 1) return true;
}
return false;
}public class Solution {
public bool CanJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.Length; i++) {
if (i > maxReach) return false;
maxReach = Math.Max(maxReach, i + nums[i]);
if (maxReach >= nums.Length - 1) return true;
}
return false;
}
}In this Python implementation, we enumerate through nums while updating a tracking variable max_reach, which maintains the furthest index accessible. Since it keeps being updated based on jump length, eventually if it surpasses or reaches the last index, true is returned. If an unreachable spot is encountered, false is returned.
Time Complexity: O(n), considering one loop through the array.
Space Complexity: O(1), no additional data structures used.
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.
class Solution:
def canJump(self, nums: List[int]) -> bool:
dp = [False] * len(nums)
dp[0] = True
for i in range(len(nums)):
if dp[i]:
for j in range(1, nums[i] + 1):
if i + j < len(nums):
dp[i + j] = True
return dp[-1]class Solution {
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
if (dp[i]) {
for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {
dp[i + j] = true;
}
}
}
return dp[nums.length - 1];
}
}#include <vector>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
vector<bool> dp(nums.size(), false);
dp[0] = true;
for (int i = 0; i < nums.size(); i++) {
if (dp[i]) {
for (int j = 1; j <= nums[i] && i + j < nums.size(); j++) {
dp[i + j] = true;
}
}
}
return dp[nums.size() - 1];
}
};var canJump = function(nums) {
let dp = new Array(nums.length).fill(false);
dp[0] = true;
for (let i = 0; i < nums.length; i++) {
if (dp[i]) {
for (let j = 1; j <= nums[i] && i + j < nums.length; j++) {
dp[i + j] = true;
}
}
}
return dp[nums.length - 1];
};#include <stdbool.h>
#include <string.h>
bool canJump(int* nums, int numsSize) {
bool dp[numsSize];
memset(dp, false, sizeof(dp));
dp[0] = true;
for (int i = 0; i < numsSize; i++) {
if (dp[i]) {
for (int j = 1; j <= nums[i] && i + j < numsSize; j++) {
dp[i + j] = true;
}
}
}
return dp[numsSize - 1];
}public class Solution {
public bool CanJump(int[] nums) {
bool[] dp = new bool[nums.Length];
dp[0] = true;
for (int i = 0; i < nums.Length; i++) {
if (dp[i]) {
for (int j = 1; j <= nums[i] && i + j < nums.Length; j++) {
dp[i + j] = true;
}
}
}
return dp[nums.Length - 1];
}
}For the Python Dynamic Programming approach, prepare and examine an equivalent dp list, marking reachable indices using nested loops. The solution's final conclusion stands with the last position's value, dp[-1], whether reachable or not.
Time Complexity: O(n^2), considering k elements might require examination from each index.
Space Complexity: O(n), the size of the list storing reachability data.
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:
function canJump(nums: number[]): boolean {
let mx: number = 0;
for (let i = 0; i < nums.length; ++i) {
if (mx < i) {
return false;
}
mx = Math.max(mx, i + nums[i]);
}
return true;
}func canJump(nums []int) bool {
mx := 0
for i, x := range nums {
if mx < i {
return false
}
mx = max(mx, i+x)
}
return true
}impl Solution {
#[allow(dead_code)]
pub fn can_jump(nums: Vec<i32>) -> bool {
let n = nums.len();
let mut mx = 0;
for i in 0..n {
if mx < i {
return false;
}
mx = std::cmp::max(mx, i + (nums[i] as usize));
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), considering one loop through the array. |
| Dynamic Programming Approach | Time Complexity: O(n^2), considering k elements might require examination from each index. |
| Greedy | – |
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 |
Frequently asked questions
Is Jump Game easy or hard?
Jump Game is rated Medium because the dynamic programming idea is straightforward but recognizing the greedy optimization is less obvious. Many candidates initially attempt DP before discovering that tracking the farthest reachable index solves the problem more efficiently.
Jump Game Python/Java solution
Most implementations use the greedy strategy. Iterate through the array and track the farthest reachable index using max(farthest, i + nums[i]). This logic translates directly to Python, Java, C++, JavaScript, and other languages with identical O(n) time complexity.
How to solve Jump Game in O(n)?
Traverse the array while maintaining a variable called farthest that stores the maximum reachable index so far. For each index i, verify that i is within the reachable range and update farthest = max(farthest, i + nums[i]). If farthest reaches or passes the last index, the result is true.
What is the best approach for Jump Game?
The greedy approach is considered the best solution. It tracks the farthest index reachable while iterating through the array. If the current index ever exceeds the farthest reachable position, the end cannot be reached. This solution runs in O(n) time with O(1) extra space.
Is Jump Game asked at Google/Amazon/Meta?
Jump Game is a common interview problem at large tech companies including Google, Amazon, and Meta. It tests greedy reasoning, array traversal, and the ability to reduce a dynamic programming formulation into an optimal linear-time solution.
What data structure is used in Jump Game?
The problem primarily uses arrays since the input is an integer array of jump lengths. The greedy solution only maintains a few integer variables, while the dynamic programming approach may use an additional boolean array to track reachable positions.
What is the time complexity of Jump Game?
The optimal greedy solution runs in O(n) time because the array is scanned once while maintaining the farthest reachable index. A dynamic programming approach can take O(n^2) time since it may check multiple jump possibilities for each index.