LeetCode — 1306 Jump Game III javascript solution (Possibly fastest)

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.

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

Ideas

We know that we are performing a search mechanism. That means, we are using DFS or BFS.

To visualize the whole picture on how to tackle this problem, we can imagine there is a binary tree shown as follow.

Binary Tree of [4,2,3,0,3,1,2]

Findings:

• Orange circles are duplicated, we don’t want to go through it twice. We need a Set to check existence.
• Since it’s a binary tree, performance looks better if we use BFS.
• To perform BFS, we need a Queue.

The edge case are:

1. index < 0
2. index > arr.length-1
3. index existed in set

BFS operation

BFS travels tree level by level, which means we are processing the tree from left to right → top to bottom.

But how does the tree being constructed? We loop through the Queue and pretend there is a binary tree!

Queue operates on First-In, First-Out(FIFO) principle. We push related values to the Queue every time we process the first element in the Queue.

To perform BFS, we need the following steps.

1. Create an array — queue, initialize it with [start]
2. Use while loop to loop through the queue until there is no element inside
3. Remove the first element and store in a variable — current
4. Check if current hit the target
5. Early return if we hit
6. Add related children to the queue
7. If we can exit the while loop, that means we can’t hit the target

Code

let checkAvailable = function(maxIndex, existedSet, targetIndex){
    if (targetIndex < 0 || targetIndex > maxIndex || existedSet.has(targetIndex)) return false;
    return true;
}
/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
    // initialization
    let maxIndex = arr.length - 1;
    let queue = [];
    queue.push(start);
    let existedSet = new Set();
    
    // loop through the queue
    while (queue.length > 0){
        // target in this loop
        let current = queue.shift();
        
        // hit
        if (arr[current] === 0){
            return true;
        }
        // Add travelled index to set
        existedSet.add(current);
        
        let larger = current + arr[current];
        let smaller = current - arr[current];
        if (checkAvailable(maxIndex, existedSet, larger)){
            // Add element to the loop
            queue.push(larger);
        }
        if (checkAvailable(maxIndex, existedSet, smaller)){
            // Add element to the loop
            queue.push(smaller);
        }
        
    }
    // We can't hit 0
    return false;
};

Result

One of the fastest solution