LeetCode 55: Jump Game

Problem Restatement

We are given an integer array nums.

We start at index 0. Each value nums[i] tells us the maximum number of steps we can jump forward from index i.

We need to return true if we can reach the last index. Otherwise, return false.

The official constraints are 1 <= nums.length <= 10^4 and 0 <= nums[i] <= 10^5.

Input and Output

Function shape:

def canJump(nums: list[int]) -> bool:
    ...

Examples

For:

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

The answer is:

True

One valid path is:

index 0 -> index 1 -> index 4

At index 0, nums[0] = 2, so we can jump to index 1.

At index 1, nums[1] = 3, so we can jump to the last index.

For:

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

The answer is:

False

We can reach index 3, but nums[3] = 0.

From index 3, we cannot move forward, so index 4 cannot be reached.

First Thought: Try Every Jump

A direct approach is to try every possible jump from every reachable index.

For example, from index i, we can try:

i + 1
i + 2
...
i + nums[i]

Then recursively check whether any of those choices can reach the last index.

This approach is natural, but it can repeat a lot of work. Many different paths may reach the same index, and then solve the same subproblem again.

Key Insight

We do not need to remember every path.

We only need to remember the farthest index we can reach so far.

Call this value:

farthest

As we scan the array from left to right:

1. If the current index is greater than farthest, we cannot even stand on this index.
2. If we can stand on this index, then we can use nums[i] to possibly extend farthest.

The update is:

farthest = max(farthest, i + nums[i])

If at any point farthest reaches or passes the last index, the answer is True.

Algorithm

Initialize:

farthest = 0

Then scan each index i.

For each index:

1. If i > farthest, return False.
2. Update farthest with i + nums[i].
3. If farthest >= len(nums) - 1, return True.

If the loop finishes, return True.

Correctness

At any point during the scan, farthest means the largest index reachable using only positions we have already processed.

Initially, only index 0 is reachable, so farthest = 0.

When we process index i, there are two cases.

If i > farthest, then index i cannot be reached from any earlier position. Since we scan from left to right, every later index is even farther away. Therefore the last index cannot be reached, and returning False is correct.

If i <= farthest, then index i is reachable. From index i, we may jump as far as i + nums[i]. Updating farthest with the maximum of the old value and this new reach preserves the meaning of farthest.

If farthest >= len(nums) - 1, the last index is reachable, so returning True is correct.

Therefore the algorithm returns True exactly when the last index can be reached.

Complexity

Implementation

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

        for i, jump in enumerate(nums):
            if i > farthest:
                return False

            farthest = max(farthest, i + jump)

            if farthest >= last:
                return True

        return True

Code Explanation

We start with:

farthest = 0

This means we can reach index 0 at the beginning.

We also store the last index:

last = len(nums) - 1

Then we scan each index and jump value:

for i, jump in enumerate(nums):

Before using nums[i], we must confirm that index i is reachable:

if i > farthest:
    return False

If i is reachable, then from i we may reach up to:

i + jump

So we update:

farthest = max(farthest, i + jump)

Once farthest reaches the last index, we can stop immediately:

if farthest >= last:
    return True

The final return handles the case where the loop completes normally:

return True

Testing

def run_tests():
    s = Solution()

    assert s.canJump([2, 3, 1, 1, 4]) is True
    assert s.canJump([3, 2, 1, 0, 4]) is False
    assert s.canJump([0]) is True
    assert s.canJump([0, 1]) is False
    assert s.canJump([2, 0, 0]) is True
    assert s.canJump([1, 0, 1, 0]) is False
    assert s.canJump([4, 0, 0, 0, 0]) is True

    print("all tests passed")

run_tests()