LeetCode Problem 55

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

LeetCode 55 - Jump Game

Problem Understanding

The problem gives us an integer array nums, where each value represents the maximum distance we are allowed to jump forward from that position.

You always start at index 0. From index i, you may jump any distance between 1 and nums[i], as long as you stay within the bounds of the array.

The goal is to determine whether it is possible to eventually reach the last index of the array.

For example, if nums = [2,3,1,1,4], then:

• From index 0, you can jump either 1 or 2 steps.
• Jumping to index 1 is enough, because nums[1] = 3, which allows reaching the final index.

The answer is true.

On the other hand, if nums = [3,2,1,0,4], every path eventually lands at index 3, where the jump length is 0. Once you reach that position, you cannot move forward anymore, so the last index becomes unreachable.

The constraints are important:

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

The array can contain up to ten thousand elements, so exponential exploration of all possible jump paths would be far too slow. We need something close to linear time.

There are several important edge cases to consider:

• An array of length 1, such as [0]. You already start at the last index, so the answer is automatically true.
• Arrays containing zeros in the middle. A zero can completely block progress if no earlier jump can bypass it.
• Very large jump values. A value larger than the remaining distance should still count as successfully reaching the end.
• Cases where you can almost reach the end, but become trapped just before it.

The problem guarantees that all numbers are non-negative, so we never need to consider backward movement.

Approaches

Brute Force Approach

The most straightforward idea is to recursively try every possible jump from every position.

From index i, we can attempt jumps of size:

• 1
• 2
• 3
• ...
• nums[i]

For each jump, we recursively check whether that path can eventually reach the end.

This works because it explores every possible valid sequence of jumps. If any path reaches the final index, the answer is true.

The problem is that the number of possible paths grows exponentially. Many positions get recomputed repeatedly. For example, different jump sequences may arrive at the same index, causing the same recursive work to happen again and again.

With an input size of up to 10^4, this approach becomes impractical.

Optimal Greedy Approach

The key observation is that we do not actually need to know the exact sequence of jumps.

Instead, we only need to know the farthest index we can currently reach.

As we scan through the array from left to right:

• If the current index is beyond the farthest reachable position, then we are stuck and cannot proceed.
• Otherwise, we update the farthest reachable index using:

$\text{farthest} = \max(\text{farthest},\ i + nums[i])$

This greedy strategy works because any index within the reachable range is accessible somehow. We do not care how we got there, only whether it is reachable.

As soon as the farthest reachable index reaches or exceeds the last position, we know the answer is true.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all possible jump paths
Optimal Greedy	O(n)	O(1)	Tracks the farthest reachable position while scanning once

Algorithm Walkthrough

1. Initialize a variable called farthest to 0.

This variable represents the farthest index we can currently reach. 2. Iterate through the array using index i.

At every step, we check whether the current position itself is reachable. 3. If i > farthest, return False.

This means the current index lies beyond our maximum reachable range. Since we cannot even stand on this index, progressing further is impossible. 4. Otherwise, update the farthest reachable index.

Compute:

$\text{farthest} = \max(\text{farthest},\ i + nums[i])$

This extends our reachable range if the current position allows a farther jump. 5. If farthest >= len(nums) - 1, return True.

Once the last index becomes reachable, we can stop immediately. 6. If the loop finishes without getting stuck, return True.

Successfully processing every reachable index means the last position can be reached.

Why it works

The algorithm maintains an important invariant:

• Before processing index i, every index up to farthest is reachable.

If we ever encounter i > farthest, then there exists a gap we cannot cross, meaning all future positions are unreachable as well.

If we continue extending farthest, then every newly covered position becomes reachable. Since the algorithm always keeps track of the maximum reachable boundary, reaching or surpassing the last index guarantees success.

Python Solution

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        last_index = len(nums) - 1

        for index, jump_length in enumerate(nums):
            if index > farthest:
                return False

            farthest = max(farthest, index + jump_length)

            if farthest >= last_index:
                return True

        return True

The implementation follows the greedy strategy directly.

The variable farthest stores the maximum reachable position discovered so far.

The loop iterates through each index and corresponding jump length. Before doing any update, the code checks whether the current index is reachable. If it is not, the function immediately returns False.

If the index is reachable, the algorithm updates the farthest reachable position using the current jump capability.

An early return is used when the last index becomes reachable. This avoids unnecessary work for large inputs.

The final return True handles cases where the loop completes naturally, such as arrays of length 1.

Go Solution

func canJump(nums []int) bool {
    farthest := 0
    lastIndex := len(nums) - 1

    for index, jumpLength := range nums {
        if index > farthest {
            return false
        }

        if index+jumpLength > farthest {
            farthest = index + jumpLength
        }

        if farthest >= lastIndex {
            return true
        }
    }

    return true
}

The Go implementation is almost identical to the Python version.

Go slices already track their length, so we compute lastIndex using len(nums) - 1.

Instead of using Python's built-in max function, the Go version performs a manual comparison before updating farthest.

Integer overflow is not a concern here because the constraints are small enough to safely fit within Go's standard int type.

Worked Examples

Example 1

Input:

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

Index	nums[i]	Farthest Before	Farthest After	Reachable?
0	2	0	2	Yes
1	3	2	4	Yes

At index 1, the farthest reachable position becomes 4, which is the last index.

The algorithm returns true.

Example 2

Input:

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

Index	nums[i]	Farthest Before	Farthest After	Reachable?
0	3	0	3	Yes
1	2	3	3	Yes
2	1	3	3	Yes
3	0	3	3	Yes
4	4	3	Cannot Process	No

When the loop reaches index 4, we find:

$4 > 3$

This means index 4 is unreachable.

The algorithm returns false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is processed exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan through the array. Every iteration does constant work, so the total runtime is proportional to the array length.

No additional data structures are allocated. The algorithm only stores a few integer variables, giving constant auxiliary space usage.

Test Cases

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        last_index = len(nums) - 1

        for index, jump_length in enumerate(nums):
            if index > farthest:
                return False

            farthest = max(farthest, index + jump_length)

            if farthest >= last_index:
                return True

        return True

solution = Solution()

assert solution.canJump([2, 3, 1, 1, 4]) is True      # standard reachable case
assert solution.canJump([3, 2, 1, 0, 4]) is False     # blocked by zero
assert solution.canJump([0]) is True                  # single element array
assert solution.canJump([2, 0, 0]) is True            # jump directly to end
assert solution.canJump([1, 0, 1, 0]) is False        # trapped before end
assert solution.canJump([5, 0, 0, 0, 0]) is True      # large initial jump
assert solution.canJump([1, 1, 1, 1, 1]) is True      # continuous small jumps
assert solution.canJump([2, 5, 0, 0]) is True         # middle large jump
assert solution.canJump([1, 2, 0, 1]) is True         # zero can be bypassed
assert solution.canJump([1, 0, 0]) is False           # cannot reach final index
assert solution.canJump([4, 0, 0, 0, 1]) is True      # exact reach to final index
assert solution.canJump([2, 0, 1, 0, 4]) is False     # unreachable tail section

Test Summary

Test	Why
[2,3,1,1,4]	Standard successful example
[3,2,1,0,4]	Standard failure example
[0]	Smallest possible input
[2,0,0]	Direct jump to end
[1,0,1,0]	Gets stuck before reaching target
[5,0,0,0,0]	Very large jump at start
[1,1,1,1,1]	Requires many small jumps
[2,5,0,0]	Large jump discovered later
[1,2,0,1]	Zero that can still be bypassed
[1,0,0]	Reachability failure near start
[4,0,0,0,1]	Exact boundary reach
[2,0,1,0,4]	Reachable prefix but unreachable ending

Edge Cases

Single Element Array

An input like [0] can be easy to mishandle.

Since the first index is also the last index, the correct answer is immediately true. No jumping is required at all.

The implementation handles this naturally because last_index becomes 0, and the initial reachable range already includes index 0.

Zero Blocking Progress

Arrays such as [3,2,1,0,4] are important because they expose incorrect assumptions about always moving forward successfully.

A naive implementation might only check whether some earlier jump is large enough locally, without realizing that every path eventually gets trapped at the zero.

The greedy algorithm correctly detects this because eventually the current index becomes larger than farthest, proving that progression is impossible.

Large Jump Values

Cases like [10,0,0,0] test whether the implementation correctly handles jumps that exceed the remaining distance.

Some incorrect solutions try to land exactly on the final index, which is unnecessary.

The algorithm only checks whether the farthest reachable index is greater than or equal to the last position, so oversized jumps work correctly.

Reachable Zero Values

Not every zero causes failure.

For example, [2,0,1] is still solvable because index 0 can jump directly to the last position.

The implementation does not treat zeros specially. It simply tracks the global reachable range, which naturally handles both harmless and blocking zeros correctly.