Jump Game

Work backward: dp[i] is true if the last index is reachable starting from i. The last index is trivially reachable from itself. For every earlier index, check every index within jump range to see if any of them is already known to reach the end.

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[-1] = True
        for i in range(n - 2, -1, -1):
            furthest = min(i + nums[i], n - 1)
            for j in range(i, furthest + 1):
                if dp[j]:
                    dp[i] = True
                    break
        return dp[0]

For each index we may scan up to nums[i] positions ahead, so the total work is O(n²) in the worst case, with O(n) space for the dp array.

Scan left to right and track the single number that matters: furthest, the farthest index reachable using jumps decided so far. At index i, if i is already beyond furthest, no earlier jump could have gotten here, so the last index is unreachable. Otherwise i is reachable, so update furthest = max(furthest, i + nums[i]).

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

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

Why it’s correct: furthest only ever needs to record the single best jump destination seen so far — the specific index that produced it never matters, because from any reachable index we could have re-derived the same or a smaller reach. Discarding “which index gave us this reach” loses no information relevant to future decisions, which is exactly what makes the greedy choice safe. Complexity: one pass, one running variable → O(n) time, O(1) space.