1306. Jump Game III

Time: O(n)

Space: O(n)

Intuition

From any position i, we can jump to i - arr[i] or i + arr[i]. This forms a graph where we want to know if position 0 is reachable. BFS naturally explores all reachable positions without redundant work.

Algorithm

1Initialise a queue with the start index.
2Mark start as visited.
3While queue is not empty:
4 Dequeue index node.
5 If arr[node] == 0, return true (reached a zero index).
6 If already visited, skip.
7 Enqueue node - arr[node] if valid.
8 Enqueue node + arr[node] if valid.
9 Mark node as visited.
10Return false if queue exhausts without finding zero.

Example Walkthrough

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

1.From 5: can jump to 5-1=4 or 5+1=6 (out of bounds, skip).
2.From 4: can jump to 4-3=1 or 4+3=7 (out of bounds).
3.From 1: can jump to 1-2=-1 (invalid) or 1+2=3.
4.From 3: arr[3]=0 → found!

Output: true

Common Pitfalls

•Do not forget the visited check; without it, infinite loops on cycles are possible.
•Bound-check both directions before enqueueing: node ± arr[node] must stay in [0, n-1].
•Early termination on finding 0 is critical; avoid processing the entire queue unnecessarily.

1306.cs

// Approach: BFS from start index. From each index i, jump to i-arr[i] or i+arr[i].
// Mark visited to avoid re-processing. Return true if any reachable index has arr[index]==0.
// Time: O(n) Space: O(n)

public class Solution
{
    public bool CanReach(int[] arr, int start)
    {
        int n = arr.Length;
        Queue<int> q = new Queue<int>();
        q.Enqueue(start);
        bool[] seen = new bool[n];

        while (q.Count > 0)
        {
            int node = q.Dequeue();
            if (arr[node] == 0)
                return true;
            if (seen[node])
                continue;
            if (node - arr[node] >= 0)
                q.Enqueue(node - arr[node]);
            if (node + arr[node] < n)
                q.Enqueue(node + arr[node]);
            seen[node] = true;
        }

        return false;
    }
}

Was this solution helpful?