DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Jump Game III

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/jump-game-iii/

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= arr.length <= 5 * 10^4
- 0 <= arr[i] < arr.length
- 0 <= start < arr.length
Enter fullscreen mode Exit fullscreen mode

Explanation

The problem is an extended version of Jump Game and Jump Game II. We can solve this using BFS or DFS approach.

In this post, we will explore the BFS way.

BFS way

We will push the starting position into a queue and start exploring its neighbours. We need to maintain a boolean array to mark the nodes we visited.

Let's check the algorithm first:

// canReach(arr, start)

- set n = arr.size()
      queue q = [start]
      int visited[n]
      int node

- loop while !q.empty()
    node = q.start()
    q.pop()

    if arr[node] == 0
      return true

    if visited[node]
      continue

    if node - arr[node] >= 0
      q.push(node - arr[node])

    if node + arr[node] < 4
      q.push(node + arr[node])

    visited[node] = true
- while end

- return false
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(N), and the space complexity is
O(n).

Let's check our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        queue<int> q{{start}};
        int node;
        vector<bool> visited(n);

        while(!q.empty()) {
            node = q.front();
            q.pop();

            if(arr[node] == 0) {
                return true;
            }

            if(visited[node]) {
                continue;
            }

            if(node - arr[node] >= 0) {
                q.push(node - arr[node]);
            }

            if(node + arr[node] < n) {
                q.push(node + arr[node]);
            }

            visited[node] = true;
        }

        return false;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func canReach(arr []int, start int) bool {
    n := len(arr)
    queue := []int{start}
    visited := make([]bool, n)

    for len(queue) != 0 {
        node := queue[0]
        queue = queue[1:]

        if arr[node] == 0 {
            return true
        }

        if visited[node] {
            continue
        }

        if node - arr[node] >= 0 {
            queue = append(queue, node - arr[node])
        }

        if node + arr[node] < n {
            queue = append(queue, node + arr[node])
        }

        visited[node] = true
    }

    return false
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var canReach = function(arr, start) {
    let n = arr.length;
    let queue = [start];
    let visited = [];
    let node;

    while(queue.length > 0) {
        node = queue[0];
        queue.shift();

        if(arr[node] == 0) {
            return true;
        }

        if(visited[node]) {
            continue;
        }

        if(node - arr[node] >= 0) {
            queue.push(node - arr[node]);
        }

        if(node + arr[node] < n) {
            queue.push(node + arr[node]);
        }

        visited[node] = true;
    }

    return false;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry run our algorithm for a given input.

Input: arr = [4, 2, 3, 0, 3, 1, 2]
       start = 5

Step 1: n = arr.size()
          = 7

        queue<int> q{{start}}
        q = [5]

        int node
        vector<bool> visited(n)

Step 2: loop while !q.empty()
        q = [5]
        true

        node = q.front()
             = 5

        q.pop()
        q = []

        if arr[node] == 0
           arr[5] == 0
           1 == 0
           false

        if visited[node]
           visited[5]
           false

        if node - arr[node] >= 0
           5 - arr[5] >= 0
           5 - 1 >= 0
           4 >= 0
           true

           q.push(node - arr[node])
           q.push(4)

           q = [4]

        if node + arr[node] < n
           5 + arr[5] < 7
           5 + 1 < 7
           6 < 7
           true

           q.push(node + arr[node])
           q.push(6)

           q = [4, 6]

        visited[node] = true
        visited[5] = true

Step 3: loop while !q.empty()
        q = [4, 6]
        true

        node = q.front()
             = 4

        q.pop()
        q = [6]

        if arr[node] == 0
           arr[4] == 0
           3 == 0
           false

        if visited[node]
           visited[4]
           false

        if node - arr[node] >= 0
           4 - arr[4] >= 0
           4 - 3 >= 0
           1 >= 0
           true

           q.push(node - arr[node])
           q.push(1)

           q = [6, 1]

        if node + arr[node] < n
           4 + arr[4] < 7
           4 + 3 < 7
           7 < 7
           false

        visited[node] = true
        visited[4] = true

Step 4: loop while !q.empty()
        q = [6, 1]
        true

        node = q.front()
             = 6

        q.pop()
        q = [1]

        if arr[node] == 0
           arr[6] == 0
           2 == 0
           false

        if visited[node]
           visited[6]
           false

        if node - arr[node] >= 0
           6 - arr[6] >= 0
           6 - 2 >= 0
           4 >= 0
           true

           q.push(node - arr[node])
           q.push(4)

           q = [1, 4]

        if node + arr[node] < n
           6 + arr[6] < 7
           6 + 2 < 7
           8 < 7
           false

        visited[node] = true
        visited[6] = true

Step 5: loop while !q.empty()
        q = [1, 4]
        true

        node = q.front()
             = 1

        q.pop()
        q = [4]

        if arr[node] == 0
           arr[1] == 0
           2 == 0
           false

        if visited[node]
           visited[1]
           false

        if node - arr[node] >= 0
           1 - arr[1] >= 0
           1 - 2 >= 0
           -1 >= 0
           false

        if node + arr[node] < n
           1 + arr[1] < 7
           1 + 2 < 7
           3 < 7
           true

           q.push(node + arr[node])
           q.push(3)

           q = [4, 3]

        visited[node] = true
        visited[1] = true

Step 6: loop while !q.empty()
        q = [4, 3]
        true

        node = q.front()
             = 4

        q.pop()
        q = [3]

        if arr[node] == 0
           arr[4] == 0
           0 == 0
           true

           return true

We return the answer as true.
Enter fullscreen mode Exit fullscreen mode

SurveyJS custom survey software

JavaScript UI Libraries for Surveys and Forms

SurveyJS lets you build a JSON-based form management system that integrates with any backend, giving you full control over your data and no user limits. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more.

Learn more

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay