Teaching Kids Programming – One-way Jump Game via Backtracking, DP and Greedy Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

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

Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

One-way Jump Game via Backtracking Algorithm

We can use Depth First Search Algorithm (Backtracking) to recursively jump until we find a path to the end. Of course, we can Breadth First Search it as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # Backtracking O(2^N)
        def dfs(j):
            if j >= n - 1:
                return True
            for i in range(1, nums[j] + 1):
                if j + i >= n:
                    break
                if dfs(j + i):
                    return True
            return False
        return dfs(0)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # Backtracking O(2^N)
        def dfs(j):
            if j >= n - 1:
                return True
            for i in range(1, nums[j] + 1):
                if j + i >= n:
                    break
                if dfs(j + i):
                    return True
            return False
        return dfs(0)

The time complexity is O(2^N) similar to Fibonacci Numbers that we repeatedly compute the intermediate dfs() value.

One-way Jump Game via Top Down Dynamic Programming Algorithm

We can remember those values so that we only calculate it once. The easiest way would be to add a @cache. Alternatively, we can construct a memo dictionary and put values into it so that we can retrieve them later.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # DFS with memoization O(N^2) = Top Down Dynamic Programming       
        @cache
        def dfs(j):
            if j >= n - 1:
                return True
            for i in range(1, nums[j] + 1):
                if j + i >= n:
                    break
                if dfs(j + i):
                    return True
            return False
        return dfs(0)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # DFS with memoization O(N^2) = Top Down Dynamic Programming       
        @cache
        def dfs(j):
            if j >= n - 1:
                return True
            for i in range(1, nums[j] + 1):
                if j + i >= n:
                    break
                if dfs(j + i):
                    return True
            return False
        return dfs(0)

Time complexity is O(N^2) as each dfs() value could be in worst case invoked N times. The space complexity is O(N) due to recursion. Recursion with Memoization is often known as Top Down Dynamic Programming Algorithm.

Bottom-up Dynamic Programming ALgorithm to Check Furthest Jump Distance

Let dp(i) represent if we can jump from i to end. Then we can compute the dp values bottom up thus dp[-1] = true, dp[-2], dp[-3] .. until we get dp[0]. If we know we can jump from i to j, and if dp[j], we set dp[i] to True.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Bottom-up Dynamic Programming
        # O(N^2)
        n = len(nums)
        dp = [False] * n
        dp[-1] = [True]
        for i in range(n - 2, -1, -1):
            reach = min(i + nums[i], n - 1)
            for j in range(i + 1, reach + 1):
                if dp[j]:
                    dp[i] = True
                    break
        return dp[0]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Bottom-up Dynamic Programming
        # O(N^2)
        n = len(nums)
        dp = [False] * n
        dp[-1] = [True]
        for i in range(n - 2, -1, -1):
            reach = min(i + nums[i], n - 1)
            for j in range(i + 1, reach + 1):
                if dp[j]:
                    dp[i] = True
                    break
        return dp[0]

Time complexity O(N^2) – space complexity O(N).

One-way Jump Game via Greedy Algorithm

We can keep tracking a furthest point that we can jump and update it if the current position is not beyond it.

1
2
3
4
5
6
7
8
9

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Greedy O(N)
        i, n = 0, len(nums)
        reach = 0
        while i < n and i <= reach:
            reach = max(reach, nums[i] + i)
            i += 1
        return reach >= n - 1        

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Greedy O(N)
        i, n = 0, len(nums)
        reach = 0
        while i < n and i <= reach:
            reach = max(reach, nums[i] + i)
            i += 1
        return reach >= n - 1        

Time complexity O(N) – linear, the space complexity is O(1) constant. Clearly, this algorithm is the best (in terms of time and space complexity).

See also other variants of jump game solutions/algorithms:

• Teaching Kids Programming – Solving the Jump Game by Depth First Search Algorithm
• Teaching Kids Programming – Revisit Breadth First Search Algorithm via a Jumping Game
• Teaching Kids Programming – One-way Jump Game via Backtracking, DP and Greedy Algorithm
• Greedy Algorithm to Reach the Last Index of the Array

–EOF (The Ultimate Computing & Technology Blog) —