Jump Game

medium
GreedyArrayDynamic ProgrammingGreedy

Given an integer array nums where each element represents the maximum jump length from that position, determine if you can reach the last index starting from the first index. You are initially positioned at the first index of the array.

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, where the jump length is 0, making it impossible to reach the last index.

Constraints

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

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

From each position, try every possible jump length from 1 to nums[i] and recursively check if any of those jumps eventually leads to the last index. This explores all possible jump sequences, resulting in exponential time because many positions are revisited from different paths.

Algorithm

  1. Start at index `0`.
  2. If the current index is the last index, return `true`.
  3. For each jump length `j` from 1 to `nums[i]`, recursively check if `index + j` can reach the end.
  4. If any jump succeeds, return `true`; otherwise, return `false`.
TimeO(2^n)SpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool canJump(vector<int>& nums) {
        return helper(nums, 0);
    }

    bool helper(vector<int>& nums, int pos) {
        if (pos == (int)nums.size() - 1) return true;
        int maxJump = min((int)nums.size() - 1, pos + nums[pos]);
        for (int next = pos + 1; next <= maxJump; next++) {
            if (helper(nums, next)) return true;
        }
        return false;
    }
};
Java 21
class Solution {
    public boolean canJump(int[] nums) {
        return helper(nums, 0);
    }

    private boolean helper(int[] nums, int pos) {
        if (pos == nums.length - 1) return true;
        int maxJump = Math.min(nums.length - 1, pos + nums[pos]);
        for (int next = pos + 1; next <= maxJump; next++) {
            if (helper(nums, next)) return true;
        }
        return false;
    }
}
Python 3.12
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        def helper(pos: int) -> bool:
            if pos == len(nums) - 1:
                return True
            max_jump = min(len(nums) - 1, pos + nums[pos])
            for next_pos in range(pos + 1, max_jump + 1):
                if helper(next_pos):
                    return True
            return False

        return helper(0)
Go 1.26
func canJump(nums []int) bool {
    var helper func(pos int) bool
    helper = func(pos int) bool {
        if pos == len(nums)-1 {
            return true
        }
        maxJump := pos + nums[pos]
        if maxJump > len(nums)-1 {
            maxJump = len(nums) - 1
        }
        for next := pos + 1; next <= maxJump; next++ {
            if helper(next) {
                return true
            }
        }
        return false
    }
    return helper(0)
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as whether index i is reachable and can eventually reach the last index. We process from right to left. For the last index, dp[n-1] = true. For each earlier index, check if any position within its jump range has dp[j] = true. If so, dp[i] = true.

Algorithm

  1. Create a boolean array `dp` of size `n` with all values `false`.
  2. Set `dp[n - 1] = true`.
  3. For each index `i` from `n - 2` down to `0`:
  4. Return `dp[0]`.
TimeO(n^2) in the worst caseSpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n, false);
        dp[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            int maxJump = min(n - 1, i + nums[i]);
            for (int j = i + 1; j <= maxJump; j++) {
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
};
Java 21
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            int maxJump = Math.min(n - 1, i + nums[i]);
            for (int j = i + 1; j <= maxJump; j++) {
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}
Python 3.12
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[n - 1] = True
        for i in range(n - 2, -1, -1):
            max_jump = min(n - 1, i + nums[i])
            for j in range(i + 1, max_jump + 1):
                if dp[j]:
                    dp[i] = True
                    break
        return dp[0]
Go 1.26
func canJump(nums []int) bool {
    n := len(nums)
    dp := make([]bool, n)
    dp[n-1] = true
    for i := n - 2; i >= 0; i-- {
        maxJump := i + nums[i]
        if maxJump > n-1 {
            maxJump = n - 1
        }
        for j := i + 1; j <= maxJump; j++ {
            if dp[j] {
                dp[i] = true
                break
            }
        }
    }
    return dp[0]
}
Approach 3

Greedy

Intuition

Track the farthest index reachable so far. Iterate through the array, and at each index, update the maximum reachable position. If at any point the current index exceeds the farthest reachable position, we are stuck and cannot proceed. If the farthest reach extends to or beyond the last index, return true.

Algorithm

  1. Initialize `maxReach = 0`.
  2. For each index `i` from 0 to `n - 1`:
  3. Return `true`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            if (i > maxReach) return false;
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= (int)nums.size() - 1) return true;
        }
        return true;
    }
};
Java 21
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 true;
    }
}
Python 3.12
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        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
Go 1.26
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
}

Frequently asked questions

What is the optimal time complexity of Jump Game?

The most efficient approach in this guide ("Greedy") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Jump Game use?

Jump Game is a medium-level Greedy problem involving Array, Dynamic Programming, Greedy. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Jump Game be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[2,3,1,1,4]
Expected Output
true