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?

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

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;
}

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

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;
}