Java DFS with Optimization (memoization)


  • 0
    S

    We can do a DFS from each position and return true when a circle is found.

    If in the current visit there isn't a circle from a starting position, we mark this position with 0, so in the next DFS when we visit this position we can stop earlier. It is the same idea as memorization, or DP.

    We mark it with 0 because an element with value 0 is guaranteed to fail.

    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && dfs(nums, i, 0) != 0) return true;
        }
        return false;
    }
    	
    private int dfs(int[] nums, int idx, int cnt) {
        if (cnt < nums.length) {
            int nidx = (idx + nums[idx] + nums.length) % nums.length;
            if (nidx == idx || nums[nidx] * nums[idx] <= 0 || dfs(nums, nidx, cnt + 1) == 0)
                nums[idx] = 0; // 0: garenteed to fail
        }
        // if have visited >= length elements, there must be a circle
        return nums[idx];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.