Problem editorial

Jump Game

MediumGreedy PatternsArrayDynamic ProgrammingGreedy

Editorial

Core insight

Jump Game · Greedy Patterns

Core Insight for Jump Game

The key intuition that transitions us from a naive simulation to an optimal greedy solution is the realization that we do not need to track how we get to an index, nor do we need to track every reachable index. We only need to track the maximum reachable index (let's call it maxReach) from the starting point.

If we can reach index i, and nums[i] allows us to jump k steps, then we can inherently reach every index between i and i + k. Therefore, the set of reachable indices is always a contiguous range starting from 0.

As we iterate through the array, we update maxReach based on the jump power at the current position. The invariant is simple: as long as the current index i is less than or equal to maxReach, we are on a valid path. If i ever exceeds maxReach, it means the current index is disconnected from the start, and the end is unreachable.

Visual Description: Imagine a "frontier" line moving across the array. Initially, the frontier is at index 0. As you visit each index up to the frontier, the value at that index may push the frontier further to the right. If your iteration catches up to the frontier and the frontier does not move forward (because the jump value is 0), you are stuck. If the frontier reaches or passes the last index, you succeed.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 55: Jump Game Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a greedy approach to track the furthest reachable index (maxReach) as we iterate through the array; if the current index exceeds maxReach, the end is unreachable.

In the LeetCode 55 problem, commonly known as Jump Game, you are provided with an array of non-negative integers. You begin at the first index of the array. Each element in the array represents the maximum jump length available at that position. Your objective is to determine if it is possible to reach the last index of the array starting from the beginning.

This is a popular interview question that tests your ability to optimize decision-making processes from exponential or quadratic time down to linear time.

Brute Force Approach for Jump Game

The naive approach to solving the Jump Game involves exploring every possible jump combination to see if any path leads to the last index. This is typically implemented using recursion or backtracking. From the current index i, we try every jump length from 1 to nums[i] and recursively check if the destination is valid.

Pseudo-code:

text

function canReach(index):
    if index == last_index:
        return true
    max_jump = nums[index]
    for jump from 1 to max_jump:
        if canReach(index + jump):
            return true
    return false

Why it fails: The time complexity of this approach is exponential, specifically $O(N^N)$ in the worst case (or $O(2^N)$ depending on jump sizes). For an array of length $10^4$ (as per constraints), the recursion tree grows excessively large, resulting in a Time Limit Exceeded (TLE) error. The algorithm repeatedly recalculates reachability for the same indices without memorizing the results.

Algorithm Strategy: Greedy Patterns

Initialize Variables: Maintain a variable maxReach initialized to 0. This represents the furthest index we can currently reach.
Iterate: Loop through the array using an index i.
Check Constraints: Before processing index i, check if i > maxReach.
- If true, it implies index i is not reachable from the start. Return false.
Update State: Update maxReach to be the maximum of its current value and i + nums[i].
- maxReach = max(maxReach, i + nums[i])
Early Exit: If maxReach is greater than or equal to the last index (n - 1), return true immediately.
Final Result: If the loop completes without returning false, return true.

Execution Flow

Consider the input nums = [2, 3, 1, 1, 4]. Length is 5. Target index is 4.

Start: maxReach = 0.
i = 0:
- Is 0 > maxReach (0)? No.
- Update maxReach: max(0, 0 + 2) = 2.
- maxReach is not $\ge 4$ . Continue.
i = 1:
- Is 1 > maxReach (2)? No.
- Update maxReach: max(2, 1 + 3) = 4.
- Check: maxReach (4) $\ge$ Target (4).
- Return True.

Consider the input nums = [3, 2, 1, 0, 4]. Target index is 4.

Start: maxReach = 0.
i = 0: maxReach becomes 0 + 3 = 3.
i = 1: maxReach becomes max(3, 1 + 2) = 3.
i = 2: maxReach becomes max(3, 2 + 1) = 3.
i = 3: maxReach becomes max(3, 3 + 0) = 3.
i = 4:
- Is 4 > maxReach (3)? Yes.
- We cannot reach index 4.
- Return False.

Proof of Correctness

The correctness relies on the "contiguous reachability" property. If we can reach index $X$ , we can reach all indices $0 \dots X$ .

Base Case: We start at index 0, so we can reach index 0.
Inductive Step: Assume we can reach all indices up to maxReach. For any valid i ( $i \le maxReach$ ), the jump nums[i] allows us to reach i + nums[i]. Since we can reach i, we can naturally reach any point between i and i + nums[i]. By taking the maximum of all i + nums[i], we extend the contiguous range of reachable indices to the new maxReach.
Conclusion: If the loop finishes or maxReach covers the last index, a path exists. If the iterator i surpasses maxReach, there is a gap in reachability that cannot be bridged.

Pattern Reuse Notes

The Greedy - Jump Game Reachability/Minimization pattern applies to several other problems. Mastering this logic is crucial for interview preparation.

LeetCode 45: Jump Game II: Instead of returning true/false, you must find the minimum number of jumps to reach the end. The pattern is similar but requires tracking the "current jump end" and "furthest reach" simultaneously.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 55

cpp

1class Solution {
2public:
3    bool canJump(vector<int>& nums) {
4        int maxReach = 0;
5        int n = nums.size();
6        
7        for (int i = 0; i < n; ++i) {
8            // If the current index is beyond our maximum reach,
9            // we cannot proceed further.
10            if (i > maxReach) {
11                return false;
12            }
13            
14            // Update the furthest reachable index
15            maxReach = max(maxReach, i + nums[i]);
16            
17            // Optimization: If we can already reach the end, return true
18            if (maxReach >= n - 1) {
19                return true;
20            }
21        }
22        
23        return true;
24    }
25};

Java Solution for LeetCode 55

java

1class Solution {
2    public boolean canJump(int[] nums) {
3        int maxReach = 0;
4        int n = nums.length;
5        
6        for (int i = 0; i < n; i++) {
7            // If current index is not reachable, we are stuck
8            if (i > maxReach) {
9                return false;
10            }
11            
12            // Update the maximum reach based on current position's jump power
13            maxReach = Math.max(maxReach, i + nums[i]);
14            
15            // Early exit if we can reach the last index
16            if (maxReach >= n - 1) {
17                return true;
18            }
19        }
20        
21        return true;
22    }
23}

Python Solution for LeetCode 55

python

1class Solution:
2    def canJump(self, nums: List[int]) -> bool:
3        max_reach = 0
4        n = len(nums)
5        
6        for i, jump in enumerate(nums):
7            # If current index is beyond reachable range
8            if i > max_reach:
9                return false
10            
11            # Update the furthest point we can reach
12            max_reach = max(max_reach, i + jump)
13            
14            # If we can reach the last index, return True immediately
15            if max_reach >= n - 1:
16                return True
17                
18        return True

AI Coach Insight

For Jump Game, focus on explaining why the structure works, not just naming Greedy Patterns.

Complexity Analysis

Time Complexity: $O(N)$ We iterate through the array nums exactly once. Each operation inside the loop (comparison and maximum calculation) takes constant time $O(1)$ .
Space Complexity: $O(1)$ We only use a single variable maxReach (and the iterator i) to store the state, regardless of the input array size. No auxiliary data structures are used.

Related Patterns

Pattern: Greedy Patterns
Subpattern: Greedy - Jump Game Reachability/Minimization

This problem fits the Greedy pattern because at every step, we only need to make the locally optimal choice—extending our maximum reach as far as possible—to determine the global outcome. We do not need to know the specific path taken, only that a path exists.

Common Mistakes & FAQ

Why does the Dynamic Programming (DP) solution result in TLE? A standard DP approach typically involves an array dp[i] indicating if index i is reachable. To fill dp[i], one might check all previous indices j < i. This results in $O(N^2)$ time complexity. Given $N \le 10^4$ , $N^2$ is $10^8$ operations, which is on the edge or too slow for strict time limits compared to the $O(N)$ greedy solution.

Why does my code fail on [0]? A common mistake is incorrectly initializing loop bounds or exit conditions. If the array has a single element [0], you are already at the last index. The logic must handle this case; a loop from 0 to n-1 with the check if maxReach >= n-1 handles this correctly as 0 >= 0 is true.

Why is checking nums[i] == 0 not sufficient to return false? Seeing a 0 does not automatically mean failure. You might be able to jump over that zero from a previous index. The failure condition is strictly i > maxReach, not the value of nums[i] itself.

Practise Jump Game and the problems around it

Jump Game is a Greedy Patterns problem, in the Jump Game Reachability/Minimization subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Jump Game · Greedy Patterns

Core Insight for Jump Game

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 55: Jump Game Solution & Explanation

Problem Overview

This is a popular interview question that tests your ability to optimize decision-making processes from exponential or quadratic time down to linear time.

Brute Force Approach for Jump Game

Pseudo-code:

text

function canReach(index):
    if index == last_index:
        return true
    max_jump = nums[index]
    for jump from 1 to max_jump:
        if canReach(index + jump):
            return true
    return false

Algorithm Strategy: Greedy Patterns

Initialize Variables: Maintain a variable maxReach initialized to 0. This represents the furthest index we can currently reach.
Iterate: Loop through the array using an index i.
Check Constraints: Before processing index i, check if i > maxReach.
- If true, it implies index i is not reachable from the start. Return false.
Update State: Update maxReach to be the maximum of its current value and i + nums[i].
- maxReach = max(maxReach, i + nums[i])
Early Exit: If maxReach is greater than or equal to the last index (n - 1), return true immediately.
Final Result: If the loop completes without returning false, return true.

Execution Flow

Consider the input nums = [2, 3, 1, 1, 4]. Length is 5. Target index is 4.

Start: maxReach = 0.
i = 0:
- Is 0 > maxReach (0)? No.
- Update maxReach: max(0, 0 + 2) = 2.
- maxReach is not $\ge 4$ . Continue.
i = 1:
- Is 1 > maxReach (2)? No.
- Update maxReach: max(2, 1 + 3) = 4.
- Check: maxReach (4) $\ge$ Target (4).
- Return True.

Consider the input nums = [3, 2, 1, 0, 4]. Target index is 4.

Start: maxReach = 0.
i = 0: maxReach becomes 0 + 3 = 3.
i = 1: maxReach becomes max(3, 1 + 2) = 3.
i = 2: maxReach becomes max(3, 2 + 1) = 3.
i = 3: maxReach becomes max(3, 3 + 0) = 3.
i = 4:
- Is 4 > maxReach (3)? Yes.
- We cannot reach index 4.
- Return False.

Proof of Correctness

The correctness relies on the "contiguous reachability" property. If we can reach index $X$ , we can reach all indices $0 \dots X$ .

Base Case: We start at index 0, so we can reach index 0.
Inductive Step: Assume we can reach all indices up to maxReach. For any valid i ( $i \le maxReach$ ), the jump nums[i] allows us to reach i + nums[i]. Since we can reach i, we can naturally reach any point between i and i + nums[i]. By taking the maximum of all i + nums[i], we extend the contiguous range of reachable indices to the new maxReach.
Conclusion: If the loop finishes or maxReach covers the last index, a path exists. If the iterator i surpasses maxReach, there is a gap in reachability that cannot be bridged.

Pattern Reuse Notes

The Greedy - Jump Game Reachability/Minimization pattern applies to several other problems. Mastering this logic is crucial for interview preparation.

LeetCode 45: Jump Game II: Instead of returning true/false, you must find the minimum number of jumps to reach the end. The pattern is similar but requires tracking the "current jump end" and "furthest reach" simultaneously.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 55

cpp

1class Solution {
2public:
3    bool canJump(vector<int>& nums) {
4        int maxReach = 0;
5        int n = nums.size();
6        
7        for (int i = 0; i < n; ++i) {
8            // If the current index is beyond our maximum reach,
9            // we cannot proceed further.
10            if (i > maxReach) {
11                return false;
12            }
13            
14            // Update the furthest reachable index
15            maxReach = max(maxReach, i + nums[i]);
16            
17            // Optimization: If we can already reach the end, return true
18            if (maxReach >= n - 1) {
19                return true;
20            }
21        }
22        
23        return true;
24    }
25};

Java Solution for LeetCode 55

java

1class Solution {
2    public boolean canJump(int[] nums) {
3        int maxReach = 0;
4        int n = nums.length;
5        
6        for (int i = 0; i < n; i++) {
7            // If current index is not reachable, we are stuck
8            if (i > maxReach) {
9                return false;
10            }
11            
12            // Update the maximum reach based on current position's jump power
13            maxReach = Math.max(maxReach, i + nums[i]);
14            
15            // Early exit if we can reach the last index
16            if (maxReach >= n - 1) {
17                return true;
18            }
19        }
20        
21        return true;
22    }
23}

Python Solution for LeetCode 55

python

1class Solution:
2    def canJump(self, nums: List[int]) -> bool:
3        max_reach = 0
4        n = len(nums)
5        
6        for i, jump in enumerate(nums):
7            # If current index is beyond reachable range
8            if i > max_reach:
9                return false
10            
11            # Update the furthest point we can reach
12            max_reach = max(max_reach, i + jump)
13            
14            # If we can reach the last index, return True immediately
15            if max_reach >= n - 1:
16                return True
17                
18        return True

Jump Game

Core insight

Core Insight for Jump Game

Full breakdown

LeetCode 55: Jump Game Solution & Explanation

Problem Overview

Brute Force Approach for Jump Game

Algorithm Strategy: Greedy Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 55

Java Solution for LeetCode 55

Python Solution for LeetCode 55

Practise Jump Game and the problems around it

Related problems

Jump Game

Core insight

Core Insight for Jump Game

Full breakdown

LeetCode 55: Jump Game Solution & Explanation

Problem Overview

Brute Force Approach for Jump Game

Algorithm Strategy: Greedy Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 55

Java Solution for LeetCode 55

Python Solution for LeetCode 55

Practise Jump Game and the problems around it

Related problems