1306. Jump Game III

 一刷 06/2022

Version #1 DFS

Time O(N)

Space O(N) - at most N times of recursion that uses system stack

Runtime: 5 ms, faster than 63.84% of Java online submissions for Jump Game III.

Memory Usage: 62.6 MB, less than 26.38% of Java online submissions for Jump Game III.

class Solution {

    public boolean canReach(int[] arr, int start) {

        boolean[] visited = new boolean[arr.length];

        return dfs(arr, start, visited);

    }

    

    private boolean dfs(int[] arr, int index, boolean[] visited) {

        if (index < 0 || index >= arr.length || visited[index]) {

            return false;

        }

        if (arr[index] == 0) {

            return true;

        }

        visited[index] = true;

        return dfs(arr, index - arr[index], visited) || dfs(arr, index + arr[index], visited);

    }

}