Jump Game

Determine if you can reach the last index of an array where each element represents the maximum jump length from that position

Language Selection

Choose your preferred programming language

Showing: Python

Jump Game

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.

Constraints:

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

Examples:

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.

Example 3:

Input: nums = [0]
Output: true
Explanation: You are already at the last index.

Approach 1: Backtracking (Brute Force)

Algorithm:

  1. Starting from index 0, try every possible jump length
  2. Recursively check if any jump leads to the last index
  3. Return true if any path succeeds

Time Complexity: O(2^n) Space Complexity: O(n) for recursion stack

Python:

def canJump(nums):
    """
    Determine if last index is reachable using backtracking
    Time: O(2^n)
    Space: O(n)
    """
    def backtrack(pos):
        if pos == len(nums) - 1:
            return True

        furthest = min(pos + nums[pos], len(nums) - 1)
        for next_pos in range(pos + 1, furthest + 1):
            if backtrack(next_pos):
                return True

        return False

    return backtrack(0)

Java:

class Solution {
    /**
     * Determine if last index is reachable using backtracking
     * Time: O(2^n)
     * Space: O(n)
     */
    public boolean canJump(int[] nums) {
        return backtrack(nums, 0);
    }

    private boolean backtrack(int[] nums, int pos) {
        if (pos == nums.length - 1) {
            return true;
        }

        int furthest = Math.min(pos + nums[pos], nums.length - 1);
        for (int next = pos + 1; next <= furthest; next++) {
            if (backtrack(nums, next)) {
                return true;
            }
        }

        return false;
    }
}

Go:

// canJump - Determine if last index is reachable using backtracking
// Time: O(2^n)
// Space: O(n)
func canJump(nums []int) bool {
    return backtrack(nums, 0)
}

func backtrack(nums []int, pos int) bool {
    if pos == len(nums)-1 {
        return true
    }

    furthest := pos + nums[pos]
    if furthest > len(nums)-1 {
        furthest = len(nums) - 1
    }

    for next := pos + 1; next <= furthest; next++ {
        if backtrack(nums, next) {
            return true
        }
    }

    return false
}

JavaScript:

/**
 * Determine if last index is reachable using backtracking
 * Time: O(2^n)
 * Space: O(n)
 */
function canJump(nums) {
    function backtrack(pos) {
        if (pos === nums.length - 1) {
            return true;
        }

        const furthest = Math.min(pos + nums[pos], nums.length - 1);
        for (let next = pos + 1; next <= furthest; next++) {
            if (backtrack(next)) {
                return true;
            }
        }

        return false;
    }

    return backtrack(0);
}

C#:

public class Solution {
    /// <summary>
    /// Determine if last index is reachable using backtracking
    /// Time: O(2^n)
    /// Space: O(n)
    /// </summary>
    public bool CanJump(int[] nums) {
        return Backtrack(nums, 0);
    }

    private bool Backtrack(int[] nums, int pos) {
        if (pos == nums.Length - 1) {
            return true;
        }

        int furthest = Math.Min(pos + nums[pos], nums.Length - 1);
        for (int next = pos + 1; next <= furthest; next++) {
            if (Backtrack(nums, next)) {
                return true;
            }
        }

        return false;
    }
}

Approach 2: Dynamic Programming (Top-Down with Memoization)

Algorithm:

  1. Use a memo array to track whether each index is “good” (can reach end), “bad”, or “unknown”
  2. Recursively check each position, caching results
  3. An index is “good” if any reachable index from it is also “good”

Time Complexity: O(n^2) Space Complexity: O(n)

Python:

def canJump(nums):
    """
    Determine if last index is reachable using dynamic programming
    Time: O(n^2)
    Space: O(n)
    """
    n = len(nums)
    # 0 = unknown, 1 = good, -1 = bad
    memo = [0] * n
    memo[n - 1] = 1

    def dp(pos):
        if memo[pos] != 0:
            return memo[pos] == 1

        furthest = min(pos + nums[pos], n - 1)
        for next_pos in range(pos + 1, furthest + 1):
            if dp(next_pos):
                memo[pos] = 1
                return True

        memo[pos] = -1
        return False

    return dp(0)

Java:

class Solution {
    /**
     * Determine if last index is reachable using dynamic programming
     * Time: O(n^2)
     * Space: O(n)
     */
    public boolean canJump(int[] nums) {
        int n = nums.length;
        // 0 = unknown, 1 = good, -1 = bad
        int[] memo = new int[n];
        memo[n - 1] = 1;

        return dp(nums, 0, memo);
    }

    private boolean dp(int[] nums, int pos, int[] memo) {
        if (memo[pos] != 0) {
            return memo[pos] == 1;
        }

        int furthest = Math.min(pos + nums[pos], nums.length - 1);
        for (int next = pos + 1; next <= furthest; next++) {
            if (dp(nums, next, memo)) {
                memo[pos] = 1;
                return true;
            }
        }

        memo[pos] = -1;
        return false;
    }
}

Go:

// canJump - Determine if last index is reachable using DP
// Time: O(n^2)
// Space: O(n)
func canJump(nums []int) bool {
    n := len(nums)
    // 0 = unknown, 1 = good, -1 = bad
    memo := make([]int, n)
    memo[n-1] = 1

    var dp func(int) bool
    dp = func(pos int) bool {
        if memo[pos] != 0 {
            return memo[pos] == 1
        }

        furthest := pos + nums[pos]
        if furthest > n-1 {
            furthest = n - 1
        }

        for next := pos + 1; next <= furthest; next++ {
            if dp(next) {
                memo[pos] = 1
                return true
            }
        }

        memo[pos] = -1
        return false
    }

    return dp(0)
}

JavaScript:

/**
 * Determine if last index is reachable using dynamic programming
 * Time: O(n^2)
 * Space: O(n)
 */
function canJump(nums) {
    const n = nums.length;
    // 0 = unknown, 1 = good, -1 = bad
    const memo = new Array(n).fill(0);
    memo[n - 1] = 1;

    function dp(pos) {
        if (memo[pos] !== 0) {
            return memo[pos] === 1;
        }

        const furthest = Math.min(pos + nums[pos], n - 1);
        for (let next = pos + 1; next <= furthest; next++) {
            if (dp(next)) {
                memo[pos] = 1;
                return true;
            }
        }

        memo[pos] = -1;
        return false;
    }

    return dp(0);
}

C#:

public class Solution {
    /// <summary>
    /// Determine if last index is reachable using dynamic programming
    /// Time: O(n^2)
    /// Space: O(n)
    /// </summary>
    public bool CanJump(int[] nums) {
        int n = nums.Length;
        // 0 = unknown, 1 = good, -1 = bad
        int[] memo = new int[n];
        memo[n - 1] = 1;

        return Dp(nums, 0, memo);
    }

    private bool Dp(int[] nums, int pos, int[] memo) {
        if (memo[pos] != 0) {
            return memo[pos] == 1;
        }

        int furthest = Math.Min(pos + nums[pos], nums.Length - 1);
        for (int next = pos + 1; next <= furthest; next++) {
            if (Dp(nums, next, memo)) {
                memo[pos] = 1;
                return true;
            }
        }

        memo[pos] = -1;
        return false;
    }
}

Approach 3: Greedy (Optimal)

Algorithm:

  1. Track the furthest reachable index as we scan left to right
  2. At each position, update the furthest reachable index: maxReach = max(maxReach, i + nums[i])
  3. If we ever reach a position beyond our current maxReach, we are stuck
  4. If maxReach reaches or exceeds the last index, return true

Time Complexity: O(n) Space Complexity: O(1)

Python:

def canJump(nums):
    """
    Determine if last index is reachable using greedy approach
    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 True

Java:

class Solution {
    /**
     * Determine if last index is reachable using greedy approach
     * Time: O(n)
     * Space: O(1)
     */
    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 true;
    }
}

Go:

// canJump - Determine if last index is reachable using greedy
// Time: O(n)
// Space: O(1)
func canJump(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 true
}

JavaScript:

/**
 * Determine if last index is reachable using greedy approach
 * Time: O(n)
 * Space: O(1)
 */
function canJump(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 true;
}

C#:

public class Solution {
    /// <summary>
    /// Determine if last index is reachable using greedy approach
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    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 true;
    }
}

Key Insights

  1. Greedy Reachability: At each index, we greedily extend the maximum reachable position. If we can never be stuck, we can reach the end.

  2. No Need to Track Path: We only care about whether the end is reachable, not the actual path taken. This makes greedy sufficient.

  3. Single Pass Sufficiency: By maintaining the furthest reachable index, we can determine reachability in a single left-to-right scan.

  4. Zero Trap: The only way to get stuck is encountering a zero that no previous position can jump over.

  5. Evolution of Approaches: Backtracking explores all paths (exponential), DP eliminates redundant subproblems (quadratic), greedy reduces to a single variable (linear).

Edge Cases

  • Single element: [0] → true (already at the last index)
  • All zeros: [0,0,0] → false (stuck at index 0, unless length is 1)
  • Large first jump: [10,0,0,0,0] → true
  • Decreasing values: [4,3,2,1,0] → true (first element can reach the end)
  • Zero in the middle: [2,0,0] → true (can jump over the zeros from index 0)
  • Unreachable due to zero wall: [1,0,1] → false

Test Cases

# Test case 1: Normal reachable case
assert canJump([2,3,1,1,4]) == True

# Test case 2: Unreachable case
assert canJump([3,2,1,0,4]) == False

# Test case 3: Single element
assert canJump([0]) == True

# Test case 4: Two elements, reachable
assert canJump([1,0]) == True

# Test case 5: Large jump at start
assert canJump([10,0,0,0,0,0]) == True

# Test case 6: All ones
assert canJump([1,1,1,1]) == True

# Test case 7: Zero blocks path
assert canJump([1,0,1]) == False

# Test case 8: Decreasing sequence
assert canJump([4,3,2,1,0]) == True

Common Mistakes

  1. Forgetting the single element case: An array of length 1 is always reachable since you start at the last index.
  2. Off-by-one in maxReach check: Comparing maxReach >= n instead of maxReach >= n - 1.
  3. Not checking i > maxReach before updating: You must verify the current position is reachable before extending from it.
  4. Iterating past unreachable positions: In the greedy approach, failing to short-circuit when stuck leads to incorrect results.
  5. Confusing jump length with destination: nums[i] is the maximum jump length, not the destination index. The destination is i + nums[i].