55. Jump Game

Problem¶

Given an array nums, where nums[i] is the farthest you can jump from index i, start at index 0 and return whether you can reach the last index.

Example:

nums = [3,2,1,0,4] -> false
0 can reach up to index 3, but index 3 has value 0, so index 4 is unreachable

Key trick¶

Track the farthest index reachable while scanning left to right.

If you reach an index beyond that farthest reachable position, you are stuck.
If the farthest reachable position ever reaches or passes the last index, return true.

Trap¶

Exploring all jumps with DFS/BFS causes many repeated states and can time out.
Thinking you must choose exact jumps is misleading; only the farthest reachable boundary matters.
Forgetting that landing on a 0 is fine if you can already jump past it.

Why is it interesting?¶

It looks like DP or graph search, but the best solution is a simple greedy invariant.

You reduce many possible paths into one state: current farthest reachable index.
It is a good test of recognizing when reachability beats path enumeration.

Python solution¶

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        # farthest index we can reach so far
        farthest = 0
        last = len(nums) - 1

        for i, jump in enumerate(nums):
            # if current index is unreachable, we are stuck
            if i > farthest:
                return False

            # extend the reachable range
            farthest = max(farthest, i + jump)

            # early exit if last index is already reachable
            if farthest >= last:
                return True

        return True

Comment on my solution¶

Your solution times out because it explores too many duplicate states.

From one index, you push many next indices.
Those indices can be reached again from other paths.
Without a visited set, the search grows explosively.

Even with a visited set, DFS is still worse than the greedy solution here.

You do not need to explore paths.
You only need the maximum reachable index at each step.

Also, this part does unnecessary work:

for jump in range(jumps + 1):

Trying every jump length is the core inefficiency.
The greedy insight avoids that entire loop.

If you wanted to keep a graph-style approach, you would at least need visited tracking:

visited = set([0])

But for interviews, the greedy solution is the right answer with \(O(n)\) time and \(O(1)\) space.

## Solution
# Implemented after reading AI comments
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        # [2,3,1,1,4] -> True
        # [3,2,1,0,4] -> False
        max_idx = 0 # maximum idx in nums that can't be reach so far
        for i in range(len(nums)):
            if i > max_idx:
                return False
            max_idx = max(max_idx, i + nums[i])
            if len(nums) - 1 <= max_idx:
                return True

# Time Limit Exceeded (79 / 178 testcases passed)
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        # [2,3,1,1,4] -> True
        # [3,2,1,0,4] -> False
        # - problem part of DP section but it seems that
        #   DFS + backtracking could work
        # - What is the minimal state to keep track
        # - maybe just use stack with (pos, jumps)
        #   - check if any jump from pos gets you to last index
        #   - if not but pos after jump in nums range push it on the stack
        #   - I think I just describe DFS
        stack = [(0, nums[0])] # (pos, jumps)
        while stack:
            pos, jumps = stack.pop()
            for jump in range(jumps + 1):
                new_pos = pos + jump
                if new_pos == len(nums) - 1:
                    return True
                if new_pos != pos and new_pos < len(nums):
                    stack.append((new_pos, nums[new_pos]))
        return False

Solution().canJump([2,3,1,1,4]) # True
Solution().canJump([3,2,1,0,4]) # False
Solution().canJump([2,5,0,0])   # True