<p>You are playing a game involving a <strong>circular</strong> array of non-zero integers <code>nums</code>. Each <code>nums[i]</code> denotes the number of indices forward/backward you must move if you are located at index <code>i</code>:</p>

<ul>
	<li>If <code>nums[i]</code> is positive, move <code>nums[i]</code> steps <strong>forward</strong>, and</li>
	<li>If <code>nums[i]</code> is negative, move <code>nums[i]</code> steps <strong>backward</strong>.</li>
</ul>

<p>Since the array is <strong>circular</strong>, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.</p>

<p>A <strong>cycle</strong> in the array consists of a sequence of indices <code>seq</code> of length <code>k</code> where:</p>

<ul>
	<li>Following the movement rules above results in the repeating index sequence <code>seq[0] -&gt; seq[1] -&gt; ... -&gt; seq[k - 1] -&gt; seq[0] -&gt; ...</code></li>
	<li>Every <code>nums[seq[j]]</code> is either <strong>all positive</strong> or <strong>all negative</strong>.</li>
	<li><code>k &gt; 1</code></li>
</ul>

<p>Return <code>true</code><em> if there is a <strong>cycle</strong> in </em><code>nums</code><em>, or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/01/img1.jpg" style="width: 402px; height: 289px;" />
<pre>
<strong>Input:</strong> nums = [2,-1,1,2,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --&gt; 2 --&gt; 3 --&gt; 0 --&gt; ..., and all of its nodes are white (jumping in the same direction).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/01/img2.jpg" style="width: 402px; height: 390px;" />
<pre>
<strong>Input:</strong> nums = [-1,-2,-3,-4,-5,6]
<strong>Output:</strong> false
<strong>Explanation:</strong> The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
The only cycle is of size 1, so we return false.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/01/img3.jpg" style="width: 497px; height: 242px;" />
<pre>
<strong>Input:</strong> nums = [1,-1,5,1,4]
<strong>Output:</strong> true
<strong>Explanation:</strong> The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --&gt; 1 --&gt; 0 --&gt; ..., and while it is of size &gt; 1, it has a node jumping forward and a node jumping backward, so <strong>it is not a cycle</strong>.
We can see the cycle 3 --&gt; 4 --&gt; 3 --&gt; ..., and all of its nodes are white (jumping in the same direction).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5000</code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>nums[i] != 0</code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you solve it in <code>O(n)</code> time complexity and <code>O(1)</code> extra space complexity?</p>

class Solution {
public:
    // time complexity -> O(n^2)
    static int calcidx( int idx, bool dir, const vector<int> &arr )
    {
        bool currdir = arr[idx] > 0 ? true : false ;
        if( currdir != dir )
            return -1 ;
        int size = arr.size() ;
        int index = (arr[idx] + idx) % size;
        if( index < 0 )
            index = ( index + size ) % size ;
        
        if( idx == index )
            return -1 ;//one element cycle
        
        return index ;
    }
    
    bool circularArrayLoop(vector<int>& nums) {
        int slow = 0 ;
        int fast = 0 ;
        bool dir = false ;
        unordered_set<int> uset ;
        vector<int> arr = nums ;
        
        for( int i = 0 ; i < arr.size() ; i++ )
        {
            if( uset.find(i) != uset.end() )
                continue ;
            slow = i ;
            fast = i ;
            
            dir = ( arr[i] > 0 ) ? true : false ;
            do
            {
                slow = calcidx(slow,dir,arr);
                uset.insert(slow);
                fast = calcidx(fast,dir,arr) ;
                uset.insert(fast);
                if( fast != -1 )
                {
                    fast = calcidx(fast,dir,arr) ;
                    uset.insert(fast);
                }
            }while(( slow != -1 ) && ( fast != -1 ) && ( slow != fast));
            
            if( ( slow != -1 ) && ( slow == fast ))
                return true;
        }

        return false ;
    }
};
9700