Teaching Kids Programming – Revisit Breadth First Search Algorithm via a Jumping Game

Teaching Kids Programming: Videos on Data Structures and Algorithms

BFS (Breadth First Search) is one of the most classic algorithms in Computer Science.

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 BFS Algorithm to Solve the Jumping Game Puzzle

We can search the steps in BFS (Breadth First Search). The key part is not to search those steps that have been explored otherwise we will end up in endless cycles.

We can remember the positions in the hash set. And if the next step is still int the range, we need to push it to the queue.

We either reach the destination (value zero) or run out of the steps in the queue (empty).

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

def bfs(n, s):
    seen = set()
    if len(n) == 0:
        return False
    q = [s]
    while len(q) > 0:
        curPos = q.pop(0)
        if n[curPos ] == 0:
            return True
        for i in [-1, 1]: # jumping forward or backward
            next = curPos + i * n[curPos]
            # not visited and next position is within the boundaries.
            if (next not in seen) and (next >= 0) and (next < len(n)):
                q.append(next)
            seen.add(next)
    return False

def bfs(n, s):
    seen = set()
    if len(n) == 0:
        return False
    q = [s]
    while len(q) > 0:
        curPos = q.pop(0)
        if n[curPos ] == 0:
            return True
        for i in [-1, 1]: # jumping forward or backward
            next = curPos + i * n[curPos]
            # not visited and next position is within the boundaries.
            if (next not in seen) and (next >= 0) and (next < len(n)):
                q.append(next)
            seen.add(next)
    return False

Please note, you can solve this problem using DFS (Depth First Search) Algorithm: Teaching Kids Programming – Solving the Jump Game by Depth First Search Algorithm

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