Solutions

# Greedy (from start: checking gas exhaustion) or from end (checking if we can jump to the end from each position). Or DP.
# greedy

# Greedy, from end - O(n) time, O(1) space
def canJump(nums: list[int]) -> bool:
    goal = len(nums) -1

    for i in range(len(nums)-2, -1, -1):
        if i + nums[i] >= goal:
            goal = i
    
    return goal == 0

# Greedy, gas station - O(n) time, O(1) space
# Each item is a gas station, can replace the tank with number of liters a the item.
# If you run out of gas you can't reach the end.
def canJump(nums: list[int]) -> bool:
    gas = nums[0]
    for g in nums[1:]:
        if gas == 0:
            return False

        gas = max(gas-1, g) # gas-1 because we consume 1 liter by moving ahead of 1
    return True


# Recursion w/o memoization - O(n!) time, O(n) space
# Recursion w/ memoization (top-down DP) - O(n^2) time, O(n) space
def canJump(nums: list[int]) -> bool:
    memo = {}

    def canJumpFromPos(pos: int) -> bool:
        if pos in memo:
            return memo[pos]
        elif pos == len(nums)-1:
            return True
        elif nums[pos] == 0:
            return False

        farthest = min(len(nums)-1, pos + nums[pos])
        for i in range(pos+1, farthest+1):
            if canJumpFromPos(i):
                memo[pos] = True
                return True
        memo[pos] = False
        return False

    return canJumpFromPos(0)

# Bottom-up DP - O(n^2) time, O(n) space
def canJump(nums: list[int]) -> bool:
    N = len(nums)
    dp = [False] * N
    dp[-1] = True # Base case: last position can reach itself

    for i in range(N-2, -1, -1):
        farthest = min(N-1, nums[i] + i)
        for j in range(i + 1, farthest+1):
            if dp[j]:
                dp[i] = True
                break

    return dp[0]