# 457. Circular Array Loop

You are given a **circular** array `nums` of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it's negative (-k), move backward k steps. Since the array is circular, you may assume that the last element's next element is the first element, and the first element's previous element is the last element.

Determine if there is a loop (or a cycle) in `nums`. A cycle must start and end at the same index and the cycle's length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

**Example 1:**

```
Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.
```

**Example 2:**

```
Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.
```

**Example 3:**

```
Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.
```

**Note:**

1. -1000 ≤ nums\[i] ≤ 1000
2. nums\[i] ≠ 0
3. 1 ≤ nums.length ≤ 5000

**Follow up:**

Could you solve it in **O(n)** time complexity and **O(1)** extra space complexity?

{% hint style="info" %}
第一個是naive的暴力解，重複利用tmp array，每一個新的start index就從input nums複製資料到tmp裡，只要tmp掃過的element就設為0。j是走在前面的那個位置。
{% endhint %}

```cpp
bool circularArrayLoop(vector<int>& nums) { // time: O(n); space: O(n)
    if (nums.empty()) return false;
    int n = nums.size();
    vector<int> tmp; // memory re-usage
    for (int i = 0; i < n; ++i) {
        tmp = nums;
        if (tmp[i] == 0) continue;
        int cur = tmp[i];
        tmp[i] = 0;
        int j = ((cur + i) % n + n) % n;
        if (j == i) continue; // cycle length is 1
        while (cur * tmp[j] > 0) { // check if the direction is the same
            cur = tmp[j];
            tmp[j] = 0;
            j = ((cur + j) % n + n) % n;
        }
        if (j == i) return true;
    }
    return false;
}
```

{% hint style="info" %}
利用快慢pointers，有點類似circular linked list在找有沒有circle。每一個start index如果沒找到cycle，那麼把掃過的elements全部設為0，這樣避免之後的loop在走過浪費時間。
{% endhint %}

```cpp
int getNextIdx(int i, const vector<int>& nums) {
    int n = nums.size();
    return ((i + nums[i]) % n + n) % n;
}
bool circularArrayLoop(vector<int>& nums) { // time: O(n); space: O(1)
    if (nums.empty()) return false;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int slow = i, fast = getNextIdx(i, nums);
        while (nums[fast] * nums[i] > 0 && nums[getNextIdx(fast, nums)] * nums[i] > 0) {
            if (slow == fast) {
                if (slow == getNextIdx(slow, nums)) break; // cycle length is 1
                return true;
            }
            slow = getNextIdx(slow, nums);
            fast = getNextIdx(getNextIdx(fast, nums), nums);
        }
        // If not found, set all elements along to 0
        slow = i;
        while (nums[slow] * nums[i] > 0) {
            int next = getNextIdx(slow, nums);
            nums[slow] = 0;
            slow = next;
        }
    }
    return false;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/457.-circular-array-loop.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.