Jump Game

Problem Statement

Given an integer array nums where you are initially positioned at the array’s first index, each element in the array represents your maximum jump length from that position.

Return true if you can reach the last index, or false otherwise.

What to notice first

• Each position tells you the maximum jump length, not the exact distance. You can jump shorter or not at all.
• The greedy approach tracks the furthest index you can reach working backwards.
• The forward DP approach tracks the furthest reachable index as you scan left to right.
• Both achieve O(n) time with O(1) space — no need for memoization tables.

Examples

Input	Output	Explanation
[2, 3, 1, 1, 4]	true	Jump 1 step from index 0 to 1, then 3 steps to the last index.
[3, 2, 1, 0, 4]	false	You always arrive at index 3; its max jump length is 0, so you cannot reach the last index.
[0]	true	Already at the last index.
[2, 0, 0]	true	Jump 1 step from index 0 to 1, then no more jumps needed.
[0, 2, 3]	false	Stuck at index 0; can only jump 0 steps.

Constraints

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Real-World Applications

Where this pattern appears

• Video playback skipping — user can jump to any point within the remaining video duration; determine if they can reach the end.
• Game level progression — each level grants ability to skip forward a certain number of levels; can the player reach the final level?
• Resource allocation — each task grants a token to spend on skipping future tasks; can all tasks be completed?
• Network hop count — each router can forward packets a certain number of hops; can a packet reach its destination?

Complexity Comparison

Approach	Time	Space	Best When
Greedy (Backwards)	O(n)	O(1)	You want the most intuitive backwards-thinking approach
DP (Forward)	O(n)	O(1)	You prefer forward iteration or early termination optimization

Both approaches are equally efficient and optimal.

Most Intuitive

Greedy Backwards

O(n) time · O(1) space

Forward Scanning

DP Forward

O(n) time · O(1) space

Approach 1: Greedy (Backwards)

★ Recommended

Start at the last index and work backwards. Track the leftmost “good” index that can reach the end. If you can reach index 0, you can reach the last index from the start.

The key insight: if you’re at position i and your max jump is nums[i], you can reach any position from i to i + nums[i]. Working backwards, you ask: “Can I reach my current good index from this position?”

⏱ Time O(n) Single backwards pass 💾 Space O(1) Only counter variable

Step-by-step Example

Input: nums = [2, 3, 1, 1, 4]

Step	i	nums[i]	Reach (i + nums[i])	Can reach lastGood?	lastGoodIndex
1	4	4	8	—	4
2	3	1	4	✓ (4 >= 4)	3
3	2	1	3	✓ (3 >= 3)	2
4	1	3	4	✓ (4 >= 2)	1
5	0	2	2	✓ (2 >= 1)	0

Result: lastGoodIndex == 0, so return true ✓

Input: nums = [3, 2, 1, 0, 4]

Step	i	nums[i]	Reach (i + nums[i])	Can reach lastGood?	lastGoodIndex
1	4	4	8	—	4
2	3	0	3	✗ (3 < 4)	4
3	2	1	3	✗ (3 < 4)	4
4	1	2	3	✗ (3 < 4)	4
5	0	3	3	✗ (3 < 4)	4

Result: lastGoodIndex == 4 != 0, so return false ✓

Animated walkthrough

How the backwards greedy approach finds reachability

Watch the lastGoodIndex shrink as we move backwards through the array. When we reach index 0, we know the answer.

Back Autoplay Next Reset

Step 1 of 5 Target: Backwards Greedy

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function canJumpGreedy(nums):
    lastGoodIndex = len(nums) - 1
    for i from len(nums) - 2 down to 0:
        if i + nums[i] >= lastGoodIndex:
            lastGoodIndex = i
    return lastGoodIndex == 0

Solution Code

Python

jump_game_greedy.py

from typing import List


def can_jump_greedy(nums: List[int]) -> bool:
    """
    Greedy approach: work backwards from the end to find the furthest index
    we can reach. If we can reach index 0, we can reach the end.

    Time: O(n), Space: O(1)
    """
    last_good_index = len(nums) - 1
    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= last_good_index:
            last_good_index = i
    return last_good_index == 0


# Test cases
print(can_jump_greedy([2, 3, 1, 1, 4]))  # True
print(can_jump_greedy([3, 2, 1, 0, 4]))  # False
print(can_jump_greedy([0]))  # True
print(can_jump_greedy([2, 0, 0]))  # True
print(can_jump_greedy([0, 2, 3]))  # False

C++

jump_game_greedy.cpp

#include <iostream>
#include <vector>
#include <algorithm>

bool canJumpGreedy(std::vector<int>& nums) {
    /*
     * Greedy approach: work backwards from the end to find the furthest index
     * we can reach. If we can reach index 0, we can reach the end.
     *
     * Time: O(n), Space: O(1)
     */
    int lastGoodIndex = (int)nums.size() - 1;
    for (int i = (int)nums.size() - 2; i >= 0; i--) {
        if (i + nums[i] >= lastGoodIndex) {
            lastGoodIndex = i;
        }
    }
    return lastGoodIndex == 0;
}

int main() {
    std::vector<int> nums1 = {2, 3, 1, 1, 4};
    std::vector<int> nums2 = {3, 2, 1, 0, 4};
    std::vector<int> nums3 = {0};
    std::vector<int> nums4 = {2, 0, 0};
    std::vector<int> nums5 = {0, 2, 3};

    std::cout << std::boolalpha;
    std::cout << canJumpGreedy(nums1) << std::endl;  // true
    std::cout << canJumpGreedy(nums2) << std::endl;  // false
    std::cout << canJumpGreedy(nums3) << std::endl;  // true
    std::cout << canJumpGreedy(nums4) << std::endl;  // true
    std::cout << canJumpGreedy(nums5) << std::endl;  // false

    return 0;
}

Java

jump_game_greedy.java

public class JumpGameGreedy {

    /**
     * Greedy approach: work backwards from the end to find the furthest index
     * we can reach. If we can reach index 0, we can reach the end.
     *
     * Time: O(n), Space: O(1)
     */
    public static boolean canJumpGreedy(int[] nums) {
        int lastGoodIndex = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastGoodIndex) {
                lastGoodIndex = i;
            }
        }
        return lastGoodIndex == 0;
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};
        int[] nums3 = {0};
        int[] nums4 = {2, 0, 0};
        int[] nums5 = {0, 2, 3};

        System.out.println(canJumpGreedy(nums1));  // true
        System.out.println(canJumpGreedy(nums2));  // false
        System.out.println(canJumpGreedy(nums3));  // true
        System.out.println(canJumpGreedy(nums4));  // true
        System.out.println(canJumpGreedy(nums5));  // false
    }
}

JavaScript

jump_game_greedy.js

/**
 * Greedy approach: work backwards from the end to find the furthest index
 * we can reach. If we can reach index 0, we can reach the end.
 *
 * Time: O(n), Space: O(1)
 */
function canJumpGreedy(nums) {
    let lastGoodIndex = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= lastGoodIndex) {
            lastGoodIndex = i;
        }
    }
    return lastGoodIndex === 0;
}

// Test cases
console.log(canJumpGreedy([2, 3, 1, 1, 4]));  // true
console.log(canJumpGreedy([3, 2, 1, 0, 4]));  // false
console.log(canJumpGreedy([0]));              // true
console.log(canJumpGreedy([2, 0, 0]));        // true
console.log(canJumpGreedy([0, 2, 3]));        // false

Rust

jump_game_greedy.rs

/// Greedy approach: work backwards from the end to find the furthest index
/// we can reach. If we can reach index 0, we can reach the end.
///
/// Time: O(n), Space: O(1)
pub fn can_jump_greedy(nums: Vec<i32>) -> bool {
    let mut last_good_index = nums.len() - 1;
    for i in (0..nums.len() - 1).rev() {
        if i + nums[i] as usize >= last_good_index {
            last_good_index = i;
        }
    }
    last_good_index == 0
}

fn main() {
    println!("{}", can_jump_greedy(vec![2, 3, 1, 1, 4]));  // true
    println!("{}", can_jump_greedy(vec![3, 2, 1, 0, 4]));  // false
    println!("{}", can_jump_greedy(vec![0]));              // true
    println!("{}", can_jump_greedy(vec![2, 0, 0]));        // true
    println!("{}", can_jump_greedy(vec![0, 2, 3]));        // false
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_can_jump_greedy() {
        assert_eq!(can_jump_greedy(vec![2, 3, 1, 1, 4]), true);
        assert_eq!(can_jump_greedy(vec![3, 2, 1, 0, 4]), false);
        assert_eq!(can_jump_greedy(vec![0]), true);
        assert_eq!(can_jump_greedy(vec![2, 0, 0]), true);
        assert_eq!(can_jump_greedy(vec![0, 2, 3]), false);
    }
}

Go

jump_game_greedy.go

package main

import "fmt"

// Greedy approach: work backwards from the end to find the furthest index
// we can reach. If we can reach index 0, we can reach the end.
//
// Time: O(n), Space: O(1)
func canJumpGreedy(nums []int) bool {
  lastGoodIndex := len(nums) - 1
  for i := len(nums) - 2; i >= 0; i-- {
    if i+nums[i] >= lastGoodIndex {
      lastGoodIndex = i
    }
  }
  return lastGoodIndex == 0
}

func main() {
  fmt.Println(canJumpGreedy([]int{2, 3, 1, 1, 4}))  // true
  fmt.Println(canJumpGreedy([]int{3, 2, 1, 0, 4}))  // false
  fmt.Println(canJumpGreedy([]int{0}))              // true
  fmt.Println(canJumpGreedy([]int{2, 0, 0}))        // true
  fmt.Println(canJumpGreedy([]int{0, 2, 3}))        // false
}

Approach 2: Dynamic Programming (Forward)

🎯 Interview Favourite

Scan the array left to right, tracking the furthest index you can reach so far. If you ever encounter an index beyond your reach, you’re stuck. If you reach or pass the last index, you win.

This approach can terminate early when maxReach >= len(nums) - 1, making it slightly more efficient in practice for arrays where the end is reachable early.

⏱ Time O(n) Single forward pass 💾 Space O(1) Only counter variable

Step-by-step Example

Input: nums = [2, 3, 1, 1, 4]

Step	i	nums[i]	maxReach (before)	New maxReach	i > maxReach?	Continue?
1	0	2	0	2	✗	✓
2	1	3	2	4	✗	✓ (maxReach 4 >= 4) → return true

Input: nums = [3, 2, 1, 0, 4]

Step	i	nums[i]	maxReach (before)	New maxReach	i > maxReach?	Continue?
1	0	3	0	3	✗	✓
2	1	2	3	3	✗	✓
3	2	1	3	3	✗	✓
4	3	0	3	3	✗	✓
5	4	4	3	—	✓ → return false

At index 4, we exceed maxReach (3), so we are stuck.

Pseudocode

function canJumpDP(nums):
    maxReach = 0
    for i from 0 to len(nums) - 1:
        if i > maxReach:
            return false
        maxReach = max(maxReach, i + nums[i])
        if maxReach >= len(nums) - 1:
            return true
    return false

Solution Code

Python

jump_game_dp.py

from typing import List


def can_jump_dp(nums: List[int]) -> bool:
    """
    Dynamic programming approach: forward pass tracking the furthest
    reachable index. If we can ever reach the end index, return True.

    Time: O(n), Space: O(1)
    """
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= len(nums) - 1:
            return True
    return False


# Test cases
print(can_jump_dp([2, 3, 1, 1, 4]))  # True
print(can_jump_dp([3, 2, 1, 0, 4]))  # False
print(can_jump_dp([0]))  # True
print(can_jump_dp([2, 0, 0]))  # True
print(can_jump_dp([0, 2, 3]))  # False

C++

jump_game_dp.cpp

#include <iostream>
#include <vector>
#include <algorithm>

bool canJumpDP(std::vector<int>& nums) {
    /*
     * Dynamic programming approach: forward pass tracking the furthest
     * reachable index. If we can ever reach the end index, return True.
     *
     * Time: O(n), Space: O(1)
     */
    int maxReach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = std::max(maxReach, i + nums[i]);
        if (maxReach >= (int)nums.size() - 1) {
            return true;
        }
    }
    return false;
}

int main() {
    std::vector<int> nums1 = {2, 3, 1, 1, 4};
    std::vector<int> nums2 = {3, 2, 1, 0, 4};
    std::vector<int> nums3 = {0};
    std::vector<int> nums4 = {2, 0, 0};
    std::vector<int> nums5 = {0, 2, 3};

    std::cout << std::boolalpha;
    std::cout << canJumpDP(nums1) << std::endl;  // true
    std::cout << canJumpDP(nums2) << std::endl;  // false
    std::cout << canJumpDP(nums3) << std::endl;  // true
    std::cout << canJumpDP(nums4) << std::endl;  // true
    std::cout << canJumpDP(nums5) << std::endl;  // false

    return 0;
}

Java

jump_game_dp.java

public class JumpGameDP {

    /**
     * Dynamic programming approach: forward pass tracking the furthest
     * reachable index. If we can ever reach the end index, return true.
     *
     * Time: O(n), Space: O(1)
     */
    public static boolean canJumpDP(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;
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};
        int[] nums3 = {0};
        int[] nums4 = {2, 0, 0};
        int[] nums5 = {0, 2, 3};

        System.out.println(canJumpDP(nums1));  // true
        System.out.println(canJumpDP(nums2));  // false
        System.out.println(canJumpDP(nums3));  // true
        System.out.println(canJumpDP(nums4));  // true
        System.out.println(canJumpDP(nums5));  // false
    }
}

JavaScript

jump_game_dp.js

/**
 * Dynamic programming approach: forward pass tracking the furthest
 * reachable index. If we can ever reach the end index, return true.
 *
 * Time: O(n), Space: O(1)
 */
function canJumpDP(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;
}

// Test cases
console.log(canJumpDP([2, 3, 1, 1, 4]));  // true
console.log(canJumpDP([3, 2, 1, 0, 4]));  // false
console.log(canJumpDP([0]));              // true
console.log(canJumpDP([2, 0, 0]));        // true
console.log(canJumpDP([0, 2, 3]));        // false

Rust

jump_game_dp.rs

/// Dynamic programming approach: forward pass tracking the furthest
/// reachable index. If we can ever reach the end index, return true.
///
/// Time: O(n), Space: O(1)
pub fn can_jump_dp(nums: Vec<i32>) -> bool {
    let mut max_reach = 0;
    for i in 0..nums.len() {
        if i > max_reach {
            return false;
        }
        max_reach = max_reach.max(i + nums[i] as usize);
        if max_reach >= nums.len() - 1 {
            return true;
        }
    }
    false
}

fn main() {
    println!("{}", can_jump_dp(vec![2, 3, 1, 1, 4]));  // true
    println!("{}", can_jump_dp(vec![3, 2, 1, 0, 4]));  // false
    println!("{}", can_jump_dp(vec![0]));              // true
    println!("{}", can_jump_dp(vec![2, 0, 0]));        // true
    println!("{}", can_jump_dp(vec![0, 2, 3]));        // false
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_can_jump_dp() {
        assert_eq!(can_jump_dp(vec![2, 3, 1, 1, 4]), true);
        assert_eq!(can_jump_dp(vec![3, 2, 1, 0, 4]), false);
        assert_eq!(can_jump_dp(vec![0]), true);
        assert_eq!(can_jump_dp(vec![2, 0, 0]), true);
        assert_eq!(can_jump_dp(vec![0, 2, 3]), false);
    }
}

Go

jump_game_dp.go

package main

import "fmt"

// Dynamic programming approach: forward pass tracking the furthest
// reachable index. If we can ever reach the end index, return true.
//
// Time: O(n), Space: O(1)
func canJumpDP(nums []int) bool {
  maxReach := 0
  for i := 0; i < len(nums); i++ {
    if i > maxReach {
      return false
    }
    if i+nums[i] > maxReach {
      maxReach = i + nums[i]
    }
    if maxReach >= len(nums)-1 {
      return true
    }
  }
  return false
}

func main() {
  fmt.Println(canJumpDP([]int{2, 3, 1, 1, 4}))  // true
  fmt.Println(canJumpDP([]int{3, 2, 1, 0, 4}))  // false
  fmt.Println(canJumpDP([]int{0}))              // true
  fmt.Println(canJumpDP([]int{2, 0, 0}))        // true
  fmt.Println(canJumpDP([]int{0, 2, 3}))        // false
}

Common mistakes

Watch for these pitfalls

• Thinking you must jump exactly the max value. The number is a maximum, not a requirement. You can jump 0, 1, 2, …, or up to that many steps.
• Greedy vs. DP confusion. Both are greedy in spirit: “how far can I possibly go?” The backwards approach updates a single “good” index; the forward approach tracks a maximum. Both are O(n) with O(1) space.
• Off-by-one errors. Make sure you check i + nums[i] >= lastGoodIndex (not >), and check maxReach >= len(nums) - 1 (not ==), because you might overshoot the end.
• Not handling edge cases. A single-element array always returns true (you start at the last index). An array beginning with 0 that has length > 1 always returns false.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

jump_game_space_optimized.py

pass

C++

jump_game_space_optimized.cpp

int main() { return 0; }

Java

JumpGameSpaceOptimized.java

class 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;
    }
}

System.out.println(new Solution().canJump(new int[]{2, 3, 1, 1, 4}));

JavaScript

jump_game_space_optimized.js

export default {};

Rust

jump_game_space_optimized.rs

fn main() {}

Go

jump_game_space_optimized.go

package main
func solution() int { return 0 }

Related Problems

• Jump Game II ↗ Medium #45
• Jump Game III ↗ Medium #1306
• Jump Game VII ↗ Medium #1871

Interview Tips

Key trade-offs to discuss

• Why greedy over DP? Both are O(n) and O(1), but the backwards greedy approach is more intuitive: “work back from the goal to see if the start can reach it.”
• Early termination: The forward DP approach can exit as soon as maxReach >= len(nums) - 1, but in the worst case both are O(n).
• Why not recursion or memoization? Dynamic programming via a lookup table would use O(n) space. These greedy approaches use only O(1) space because we only care about a single value (the furthest reach or the current good index).
• Follow-up — Jump Game II: If you must return the minimum number of jumps instead of just a boolean, the greedy approach with two pointers for levels becomes useful.