Java one pass O(n), O(1): Tracks previous, startIndex and marks tested with 0


  • 0
    N
    public class Solution {
    
        public int fixIndex(int index, int length){   /** Modulo Operator */
            return (index%length+length)%length;
        }
        
        public boolean circularArrayLoop(int[] nums) { 
            int length = nums.length;
            if(length == 0) return false; 
    
            int index = 0; //current (>length or <0) index
            int previous = -1; //track previous index
            int fixedIndex= 0; //current index after mod-ing
            int startIndex = 0;  //track start of the circle loop
    
           for(int j = 0; j<length; ){ //j marks how many indices we have already tested
               
               fixedIndex = fixIndex(index, length);
               
               if(fixedIndex != fixIndex(previous, length) && fixedIndex == startIndex && fixedIndex != index ) return true;
                   /**found a circle, since 
                     - the index is != previous (not looping to itself), 
                           -it has looped back to the start of the circle, 
                                 -and it has moved forward/backward since fixedIndex != index */
               else 
               { //circle has not been found yet, 
                 //so increment index until the next not yet tested index (or not increment if 
                 //current index has not been tested
                   while(nums[ fixIndex(index, length) ]==0) {  
                       index = fixIndex(index, length); 
                       previous = index; //always set previous to current before changing index
                       index++;
                       startIndex = index; //if index has been incremented, 
                                           //then it's the start of a new circle, so reset the startIndex
                   }
               }           
    
                fixedIndex = fixIndex(index, length);
                if(nums[fixedIndex] != 0) j++; //increment number of terms tested before setting 
                previous = index;              //nums at that index to 0  (marked "over here")
               index += nums[fixedIndex ];   //move to next term
               nums[fixedIndex ] = 0;            //over here   (must move to next term first before setting this value to 0)    
           }
    
           fixedIndex = fixIndex(index, length); //updating fixedIndex to reflect index's new value after loop
           if(  fixedIndex != fixIndex(previous, length) && fixedIndex == startIndex &&  fixedIndex != index) return true;
           //^ final check for if the end of the circle is the last index checked
    
            return false; //circle was not found :c
        }
    
    }
    

Log in to reply
 

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