[LeetCode] 1306. Jump Game III

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

A typical BFS problem. In case it encounters a loop during the traversal, it is impossible to reach to the position with value 0.

Time complexity = O ( N ).   N = length of the arr. Because we need to every item in the input array at least once.

class Solution {
    public boolean canReach(int[] arr, int start) {
        if (arr[start] == 0) return true;
        
        int N = arr.length;
        boolean[] visited = new boolean[N];
        visited[start] = true;
        
        Queue<Integer> queue = new LinkedList();
        queue.offer(start);
        
        int[] diffs = new int[] {1, -1};
        
        while (!queue.isEmpty()) {
            int index = queue.poll();
                        
            for (int d : diffs) {
                int next  = index + d * arr[index];
                if (next >= 0 && next < N && !visited[next]) {
                    if (arr[next] == 0) return true;

                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        
        return false;
    }
}