Java Solution- Similar to Finding LinkedList Cycle


  • 1

    Start from any index, move to the next index by function f(i)=((i+nums[i])%len+len)%len where len is the length of array nums. and follow the chain. We are guaranteed there is a cycle in this chaining process. check if all the numbers in the cycle are backward or forward. Remember to exclude the one element cycle cases.

    public class Solution {
        public boolean circularArrayLoop(int[] nums) {
            if(nums==null||nums.length==0) return false;
            for(int a:nums){
                if(a==0) return false;
            }
            int len=nums.length;
            for(int i=0;i<len;i++){
                if(checkCycle(nums,i)) return true;
            }
            return false;
        }
        public boolean checkCycle(int[] nums, int start){
            int len=nums.length;
            int slow=((start+nums[start])%len+len)%len;
            int fast=((slow+nums[slow])%len+len)%len;
            while(slow!=fast){
                slow=((slow+nums[slow])%len+len)%len;
                fast=((fast+nums[fast])%len+len)%len;
                fast=((fast+nums[fast])%len+len)%len;
            }
            if(slow==((slow+nums[slow])%len+len)%len) return false;//one element loop
            boolean forward_backward=nums[slow]>0;//forward or backword
            int ptr=((slow+nums[slow])%len+len)%len;
            while(ptr!=slow){
                if(nums[ptr]>0!=forward_backward) return false;
                ptr=((ptr+nums[ptr])%len+len)%len;
            }
            return true;
        }
    }
    

Log in to reply
 

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