Teaching Kids Programming – Solving the Jump Game by Depth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Yesterday, we talked about the Breadth First Search Algorithm. We are solving the same Jump Game problem today by using the Depth First Search Algorithm.

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i – arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:

All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:
1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

Using the DFS Algorithm to Solve the Jumping Game Puzzle

Depth First Search aka. DFS algorithm searches the tree/graph as deep (vertically) as it can get then rewind (horizontally).

DFS algorithm can be used to solve the jump game as well, where we simulate the walking on a path as far as we can.

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

def dfs(n, s, vis = set()):
    if n[s] == 0: # reach destination
        return True
    for i in [-1, 1]:
        next = s + i * n[s]  # next position
        if (next not in vis) and (next >= 0) and (next < len(n)):
            vis.add(next)  # mark as visited
            if dfs(n, next, vis): # this way we can reach the destination?
                vis.remove(next)  # optional
                return True
            vis.remove(next)
    return False

def dfs(n, s, vis = set()):
    if n[s] == 0: # reach destination
        return True
    for i in [-1, 1]:
        next = s + i * n[s]  # next position
        if (next not in vis) and (next >= 0) and (next < len(n)):
            vis.add(next)  # mark as visited
            if dfs(n, next, vis): # this way we can reach the destination?
                vis.remove(next)  # optional
                return True
            vis.remove(next)
    return False

You can also solve this problem using the Breadth First Search Algorithm: Teaching Kids Programming – Revisit Breadth First Search Algorithm via a Jumping Game

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) —