A long and tedious but well commented c++ solution using floyd's cycle detection.


  • 0
    G

    This technique comes in handy in a variety of questions of this sort. Hence, it's important to master it and add it to our tool box.

    class Solution {
    public:
    
        bool RunLoop(vector<int> & nums,int start, bool direction)
        {
           int slow = start;
           int n = nums.size();
           int fast = 0;
           
           //
           // We need Prevfast as a way to know if the cycle size is > 1
           //
           
           int Prevfast = (nums[start] != 0  && (nums[start] > 0 == direction)) ? 
                (n + ((start + nums[start])%n)) %n : slow;
        
           //
           // if Prevfast leads us to a cell which is "bad" just fail
           //
           
           if(nums[Prevfast] == 0 || (nums[Prevfast] > 0 != direction))
           {
               return (false);
           }
           
           //
           // fast will point to next->next
           //
           fast = (n + ((Prevfast + nums[Prevfast]) %n ) )%n;
            
           //
           // This is the case in which we have a cycle of size 1
           // 
           
           if(fast == Prevfast)
           {
               return (false);
           }
            
           //
           // The main loop
           //
           
           while(slow != fast)
           {
               //
               // Check if slow is a "bad" cell
               //
               
               if(nums[slow] == 0 || ((nums[slow] > 0) != direction))
               {
                   return (false);
               }
               
               //
               // Check if fast is a "bad" cell
               // 
               
               if(nums[fast] == 0 || ((nums[fast] > 0) != direction))
               {
                   return (false);
               }
               
               slow = (n + ((slow + nums[slow])% n))%n;
        
               Prevfast = (n + ((fast + nums[fast])%n)) %n;
               
               if(nums[Prevfast] == 0 || ((nums[Prevfast] > 0) != direction))
               {
                   return (false);
               }
               
               fast = (n + ((Prevfast + nums[Prevfast])%n))%n;
               
               //
               // The same check as before - detect cycle of size 1
               //
               
               if(fast == Prevfast)
               {
                   return (false);
               }
           }
           
           return (true);
        }
    
        bool circularArrayLoop(vector<int>& nums) 
        {
            if(nums.empty())
            {
                return false;
            }
            
            for(int i = 0; i < nums.size(); ++i)
            {
                //
                // zero doesn't lead us anywhere
                //
                
                if(nums[i] == 0)
                {
                    continue;
                }
                
                if(nums[i] > 0)
                {
                    //
                    // Run loop with positive direction
                    //
                    
                    if(RunLoop(nums,i,true))
                    {
                        return (true);
                    }
                }
                else
                {
                    //
                    // Run loop with negative direction
                    //
                    
                    if(RunLoop(nums,i,false))
                    {
                        return (true);
                    }
                }
                
            }
            
            return (false);
        }
    };

Log in to reply
 

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