A easy solution without using two pointers


  • 0
    F

    The idea is to use a sum to record if we have ran multiple rounds of the array. Similar to the two pointers solution, we set the failed element to zero to mark that we have already tried it.

    public boolean circularArrayLoop(int[] nums) {
            int len=nums.length;
            
            if (len<2) return false;
            
            for (int i=0; i<nums.length; i++){
                nums[i]=nums[i]%len;
            }
            
            int pre=nums[0];
            int cur=0;
            int count=1;
            int sum=nums[0];
            nums[0]=0;
            
            while (count<=len){
                
                int next=(cur+pre+len)%len;
                
                // System.out.println("pre="+pre+", cur="+cur+", next="+next);
                
                if (pre*nums[next]>0){
                    sum+=nums[next];
                    if (sum%len==0) return true;
                    pre=nums[next];
                    count++;
                    nums[next]=0;  //next is visited
                    cur=next;
                }else if (nums[next]==0){
                    cur=findNext(nums, next);
                    if (cur==-1) return false;
                    pre=nums[cur];
                    sum=nums[cur];
                    nums[cur]=0;
                    count++;
                }else{
                    sum=nums[next];
                    pre=nums[next];
                    nums[next]=0;
                    cur=next;
                    count++;
                }
                    
            }
            
            
            return false;
            
        }
        
        public int findNext(int[] nums, int curIndex){
            
            int next=(curIndex+1)%nums.length;
            
            while (next!=curIndex){
                if (nums[next]!=0) return next;
                next=(next+1)%nums.length;
            }
            
            return -1;
            
        }
    
    

Log in to reply
 

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