Jump Game III

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 any index with value 0.

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

Implementation (BFS)#

• Intuition: The problem is reachability in an implicit graph — each index has at most two neighbours (i + arr[i] and i - arr[i]). BFS from start will find any index with value 0 if one is reachable, exploring all positions level by level.
• Mechanics: Indices are enqueued as candidates. For each dequeued index, both forward and backward jumps are enqueued if they are in bounds. To prevent revisiting, the element at a visited index is negated (arr[currIdx] *= -1) — a negative value signals "already visited" and causes the node to be skipped on re-encounter.
• Trade-off: Negating the array value is a clever O(1) visited-marking trick that avoids an explicit visited boolean array. It does modify the input, which may be undesirable; a separate vector<bool> visited(n, false) can be used if input mutation is forbidden, at the cost of O(n) extra space (same asymptotic result).

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if(arr[start]==0)
            return true;

        queue<int> q;
        q.push(start);

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

            if(arr[currIdx]==0)
                return true;

            if(arr[currIdx]<0)
                continue;

            if(currIdx+arr[currIdx] < arr.size())
                q.push(currIdx+arr[currIdx]);

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

            arr[currIdx] *= -1;

        }
        return false;
    }
};

Time Complexity: O(n), Each index is visited at most once because you mark it by making arr[currIdx] negative.

Space Complexity: O(n)