Java one Pointer O(n) time, O(1) space solution.


  • 0

    I use Integer.MAX_VALUE to mark the visited indexes. If there is any better way to mark the visited indexes, please share! Obviously, my solution will fail if there is any entry with 2^31 - 1.

    I thought about using two pointers but found it not necessary. My idea is simple, loop the array, choose the unvisited entry as the start of a sequence. In the while loop, check if the current index is visited, check if the direction of next step is not the same as the starting point and also check self loops. In total, each entry will be visited for at most 2 times.

    public boolean circularArrayLoop(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            int start = i;
            int direction = nums[start]>0?1:-1;//1 forward, -1 backward.
            int curr = start;
            while(true){
                if(nums[curr]==Integer.MAX_VALUE) break;
                int next = getNextIdx(nums,curr);
                if(next==curr||nums[next]*direction<0)break;
                if(next==start) return true;
                nums[curr] = Integer.MAX_VALUE;
                curr = next;
            }
        }
        return false;
    }
    private int getNextIdx(int[] nums, int i){
        int next = i+nums[i];
        next = next>=0?next%nums.length:next%nums.length + nums.length;
        return next;
    }

Log in to reply
 

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