Jump Game

Problem Statement

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false otherwise.

Example 1:

Input: nums = [1,2,0,1,0]


Output: True

Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.

Example 2:

Input: nums = [1,2,1,0,1]


Output: False

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the length of the input array.

Hint 1

Think about what it means to be able to reach the last index. Do we need to know how we reach it, or just that we can reach it?

Hint 2

Work backwards from the last index. For each index, check if you can reach the “goal” (initially the last index). If you can, then that index becomes the new “goal”.

Hint 3

If at the end, the goal is index 0, then you can reach the last index from index 0.

Solution

Recursion

def can_jump(nums: List[int]) -> bool:
    def dfs(i: int) -> bool:
        if i == len(nums) - 1:
            return True
        end = min(len(nums) - 1, i + nums[i])
        for j in range(i + 1, end + 1):
            if dfs(j):
                return True
        return False


    return dfs(0)

Time complexity: O(n!) Space complexity: O(n)

Dynamic Programming (Top-Down)

def can_jump(nums: List[int]) -> bool:
    memo = {}


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


        end = min(len(nums), i + nums[i] + 1)
        for j in range(i + 1, end):
            if dfs(j):
                memo[i] = True
                return True
        memo[i] = False
        return False


    return dfs(0)

Time complexity: O(n ^ 2) Space complexity: O(n)

Dynamic Programming (Bottom-Up)

def can_jump(nums: List[int]) -> bool:
    n = len(nums)
    dp = [False] * n
    dp[-1] = True


    for i in range(n - 2, -1, -1):
        end = min(n, i + nums[i] + 1)
        for j in range(i + 1, end):
            if dp[j]:
                dp[i] = True
                break
    return dp[0]

Time complexity: O(n ^ 2) Space complexity: O(n)

Greedy

def can_jump(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

Time complexity: O(n) Space complexity: O(1)