[LeetCode] Jump Game III

Problem: 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:

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 

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

Approach: Just by looking at it you can think of this problem of reaching from a source node to destination node in a Graph. Here the nodes are connected using "i + arr[i] or i - arr[i]" condition. We can used BFS or DFS to solve this problem. I am using DFS in my implementation.

Implementation in C#:

    public bool CanReach(int[] arr, int start)

    {

        if (arr[start] == 0)

        {

            return true;

        }

        int jump = arr[start];

        // Marking it as visited.

        arr[start] = -1;

        if (start + jump < arr.Length && arr[start + jump] != -1)

        {

            if (this.CanReach(arr, start + jump))

            {

                return true;

            }

        }

        if (start - jump >= 0 && arr[start - jump] != -1)

        {

            if (this.CanReach(arr, start - jump))

            {

                return true;

            }

        }

        return false;

    }

Complexity: O(n)