Jump Game

Description

You are given an integer array where each element represents the maximum number of positions you can jump forward from that index. You start at the first index (index 0) and need to determine whether it is possible to reach the last index of the array.

At any position i, you can jump to any index from i+1 to i+nums[i] (inclusive), as long as it does not go past the end of the array. The value nums[i] is the maximum jump length — you can choose to jump any distance from 1 to nums[i], not just exactly nums[i].

Return true if there exists at least one sequence of jumps that takes you from index 0 to the last index. Return false if no such sequence exists, meaning you will inevitably get stuck at some position where nums[i] = 0 before reaching the end.

Examples

Example 1

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

Output: true

Explanation: From index 0 (value 2), you can jump 1 step to index 1. From index 1 (value 3), you can jump 3 steps to index 4, which is the last index. So the path 0 → 1 → 4 reaches the end. There are other valid paths too, like 0 → 1 → 2 → 3 → 4, but we only need to confirm that at least one path exists.

Example 2

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

Output: false

Explanation: No matter what path you take from index 0, you will always end up at index 3 (value 0). From index 3, you cannot jump anywhere because the maximum jump length is 0. Index 4 is unreachable. For example: 0 → 1 → 2 → 3 (stuck), or 0 → 1 → 3 (stuck), or 0 → 2 → 3 (stuck), or 0 → 3 (stuck). Every possible route leads to the zero at index 3.

Example 3

Input: nums = [0]

Output: true

Explanation: The array has only one element. You start at index 0, which is also the last index. You are already at the destination, so no jumps are needed. Return true.

Constraints

1 ≤ nums.length ≤ 10^4
0 ≤ nums[i] ≤ 10^5

Editorial

Brute Force

Intuition

The most natural first approach is to try every possible sequence of jumps using recursion. From each position, you have multiple choices: you can jump 1 step, 2 steps, ..., up to nums[i] steps. If any of these choices eventually leads to the last index, the answer is true.

Think of it like navigating a series of stepping stones across a river. At each stone, there is a sign telling you the maximum number of stones ahead you can leap to. You try jumping to the nearest stone first. If that path leads to a dead end, you backtrack and try jumping to the next stone, and so on. If you exhaust all choices from a position without reaching the far bank, that position is a dead end.

This approach explores all possible paths through the array using depth-first recursion. It is correct but extremely slow because it re-explores the same subproblems many times.

Step-by-Step Explanation

Let's trace through with nums = [3, 2, 1, 0, 4]:

Step 1: Start at index 0 (value 3). We can jump 1, 2, or 3 steps. Try jumping 1 step to index 1.

Step 2: At index 1 (value 2). We can jump 1 or 2 steps. Try jumping 1 step to index 2.

Step 3: At index 2 (value 1). We can jump 1 step to index 3.

Step 4: At index 3 (value 0). We cannot jump anywhere — dead end! Backtrack to index 2.

Step 5: Index 2 has no more choices. Backtrack to index 1. Try jumping 2 steps to index 3.

Step 6: At index 3 (value 0) again. Dead end! Backtrack to index 1. No more choices. Backtrack to index 0.

Step 7: From index 0, try jumping 2 steps to index 2.

Step 8: At index 2 (value 1). Jump 1 step to index 3.

Step 9: At index 3 (value 0). Dead end! Backtrack all the way to index 0.

Step 10: From index 0, try jumping 3 steps to index 3.

Step 11: At index 3 (value 0). Dead end! All paths from index 0 exhausted. Return false.

Jump Game — Recursive Brute Force Exploration — Watch how recursion tries every possible jump path, backtracking when it hits a dead end (value 0), until all paths are exhausted.

Algorithm

Define a recursive function canReach(position):
- If position ≥ last index, return true
- For each jump size from 1 to nums[position]:
  - If canReach(position + jump) returns true, return true
- Return false (no jump from this position reaches the end)
Return canReach(0)

Code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        return canReach(nums, 0);
    }
    
private:
    bool canReach(vector<int>& nums, int pos) {
        if (pos >= nums.size() - 1) {
            return true;
        }
        
        for (int jump = 1; jump <= nums[pos]; jump++) {
            if (canReach(nums, pos + jump)) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        def can_reach(pos: int) -> bool:
            if pos >= len(nums) - 1:
                return True
            
            for jump in range(1, nums[pos] + 1):
                if can_reach(pos + jump):
                    return True
            
            return False
        
        return can_reach(0)

class Solution {
    public boolean canJump(int[] nums) {
        return canReach(nums, 0);
    }
    
    private boolean canReach(int[] nums, int pos) {
        if (pos >= nums.length - 1) {
            return true;
        }
        
        for (int jump = 1; jump <= nums[pos]; jump++) {
            if (canReach(nums, pos + jump)) {
                return true;
            }
        }
        
        return false;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

In the worst case, from each position we may try up to n-1 jumps, and each jump leads to a new recursive call that itself branches further. This creates an exponential number of paths. For an array like [n, n-1, n-2, ..., 1, 0], the recursion tree has O(2^n) nodes because each position can reach every subsequent position.

Space Complexity: O(n)

The recursion depth can go up to n in the worst case (jumping one step at a time from index 0 to index n-1), so the call stack uses O(n) space.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2^n). With n up to 10^4, this would require up to 2^10000 operations — an astronomically large number that no computer could ever complete.

The fundamental problem is that the recursion re-solves the same subproblems over and over. In our example with [3, 2, 1, 0, 4], the subproblem "can we reach the end from index 3?" was solved multiple times (once via path 0→1→2→3, once via 0→1→3, once via 0→2→3, once via 0→3). Each time, the answer was the same: no.

Key insight: if we remember (memoize) the result of each subproblem after computing it once, we never need to recompute it. This transforms the exponential recursion into a polynomial-time dynamic programming solution.

Better Approach - Dynamic Programming

Intuition

Instead of exploring every path from scratch, we can work backwards and build up our answer position by position. We create an array dp where dp[i] indicates whether we can reach the last index starting from index i.

We know dp[n-1] = true (if you are already at the last index, you have reached it). For every other position i, we check: can we jump from i to any position j where dp[j] = true? If so, dp[i] = true. Otherwise, dp[i] = false.

Think of it like planning a road trip in reverse. You start by marking the destination city as "reachable." Then you look at each city one step closer to your starting point: if any road from that city leads to a city already marked "reachable," you mark the current city as "reachable" too. After processing all cities, you check whether your starting city got marked.

This avoids redundant computation because each position is evaluated exactly once.

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 1, 4]:

Step 1: Initialize dp array of size 5. Set dp[4] = true (last index is always reachable from itself). dp = [false, false, false, false, true].

Step 2: Process index 3 (value 1). Can jump to index 4. Is dp[4] true? Yes! Set dp[3] = true. dp = [false, false, false, true, true].

Step 3: Process index 2 (value 1). Can jump to index 3. Is dp[3] true? Yes! Set dp[2] = true. dp = [false, false, true, true, true].

Step 4: Process index 1 (value 3). Can jump to indices 2, 3, or 4. Check dp[2] — it is true! Set dp[1] = true immediately (no need to check further). dp = [false, true, true, true, true].

Step 5: Process index 0 (value 2). Can jump to indices 1 or 2. Check dp[1] — it is true! Set dp[0] = true. dp = [true, true, true, true, true].

Step 6: Return dp[0] = true.

Jump Game — Bottom-Up DP Table Construction — Watch how we fill the dp array from right to left, marking each position as reachable if it can jump to any already-reachable position.

Algorithm

Create a boolean array dp of size n, initialized to false
Set dp[n-1] = true (last index is always reachable from itself)
For i from n-2 down to 0:
- For each jump size j from 1 to nums[i]:
  - If i + j < n and dp[i + j] is true, set dp[i] = true and break
Return dp[0]

Code

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--) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                if (dp[i + j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[0];
    }
};

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):
            for j in range(1, nums[i] + 1):
                if i + j < n and dp[i + j]:
                    dp[i] = True
                    break
        
        return dp[0]

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--) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                if (dp[i + j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[0];
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n positions, we may check up to n-1 jump targets in the worst case (when nums[i] is very large). This gives a worst-case of O(n²) total operations. In practice, early termination (breaking when we find a reachable target) helps, but the worst case remains quadratic.

Space Complexity: O(n)

We use a dp array of size n to store whether each position can reach the end.

Why This Approach Is Not Efficient

The DP approach is a huge improvement over brute force (O(n²) vs O(2^n)), but with n up to 10^4, it requires up to 10^8 operations in the worst case — which may be too slow for strict time limits.

The DP solution stores more information than we actually need. We maintain a full boolean array tracking reachability from every position, but we only care about position 0. More importantly, the inner loop scans up to n jump targets per position.

Key insight: instead of asking "which positions can I reach from here?", we can ask a simpler question: "what is the farthest position I can reach so far?" If we scan left to right and maintain the farthest reachable index, we can determine the answer in a single pass with no extra data structure. The farthest reachable index either keeps growing (meaning we can progress) or gets stuck (meaning we are trapped). This greedy approach eliminates both the O(n) space and the inner loop.

Optimal Approach - Greedy (Max Reach)

Intuition

The key observation is deceptively simple: if we scan the array from left to right, at each position we can update the farthest index we could possibly reach. If at any point the farthest reachable index is greater than or equal to the last index, we are done — the answer is true. Conversely, if we arrive at a position that is beyond our farthest reach, we are stuck and the answer is false.

Imagine you are driving a car along a road with gas stations. Each gas station tells you the maximum additional distance you can travel from that point. As you drive, you keep track of the farthest point your fuel can take you. If you can reach the next gas station (because it falls within your fuel range), you visit it and potentially extend your range. If a gas station is beyond your range, you run out of fuel and cannot continue.

The greedy logic works because we only need to know one thing: the maximum reach from all positions we can visit. We do not need to track specific paths or per-position reachability. At each position i that we can visit (i ≤ maxReach), we update maxReach = max(maxReach, i + nums[i]). If maxReach ever reaches or exceeds n-1, we succeed.

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 1, 4]:

Step 1: Initialize maxReach = 0. We start at index 0 and can currently reach at most index 0.

Step 2: Process index 0: is 0 ≤ maxReach (0)? Yes, we can visit it. Update maxReach = max(0, 0 + 2) = 2. We can now reach up to index 2.

Step 3: Process index 1: is 1 ≤ maxReach (2)? Yes. Update maxReach = max(2, 1 + 3) = 4. We can now reach up to index 4!

Step 4: maxReach (4) ≥ last index (4). We can reach the end! Return true immediately.

Now let's trace the failing case nums = [3, 2, 1, 0, 4]:

Step 1: Initialize maxReach = 0.

Step 2: Process index 0: 0 ≤ 0? Yes. maxReach = max(0, 0 + 3) = 3.

Step 3: Process index 1: 1 ≤ 3? Yes. maxReach = max(3, 1 + 2) = 3. No improvement.

Step 4: Process index 2: 2 ≤ 3? Yes. maxReach = max(3, 2 + 1) = 3. Still no improvement.

Step 5: Process index 3: 3 ≤ 3? Yes. maxReach = max(3, 3 + 0) = 3. The zero at index 3 contributes nothing.

Step 6: Process index 4: 4 ≤ 3? No! We cannot visit index 4 because our maximum reach is only 3. Return false.

Jump Game — Greedy Max Reach (Failing Case) — Watch how maxReach grows as we scan left to right, then stalls at index 3 where the zero blocks progress, making the last index unreachable.

Algorithm

Initialize maxReach = 0
For each index i from 0 to n-1:
a. If i > maxReach, return false (we cannot visit this index)
b. Update maxReach = max(maxReach, i + nums[i])
c. If maxReach ≥ n-1, return true (we can reach the end)
Return true

Code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= n - 1) {
                return true;
            }
        }
        
        return true;
    }
};

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        max_reach = 0
        n = len(nums)
        
        for i in range(n):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= n - 1:
                return True
        
        return True

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= n - 1) {
                return true;
            }
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array exactly once with a single for loop. At each index, we perform O(1) work: one comparison and one max operation. The total number of operations is exactly n, regardless of the values in the array.

Space Complexity: O(1)

We use only a single integer variable (maxReach) to track the farthest reachable index. No arrays, hash maps, or recursion stacks are needed. This is a significant improvement over the DP approach which used O(n) space for the dp array.

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

HARD

MEDIUM

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

MEDIUM

EASY

MEDIUM

MEDIUM

EASY

MEDIUM

Jump Game

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Dynamic Programming

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Greedy (Max Reach)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis