# 457 - Circular Array Loop

中間過程

Trial 1

一開始嘗試了自己的 fast & slow pointer 解法，可惜這個解法沒有辦法處理 [3,1,2] 這種從 index 0 無法走到 loop 起點的 case。

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        if(nums.size() < 2) return false;

        // Find the loop
        int slow = 0, fast = 0;

        do {
            slow = (slow + nums[slow]) % nums.size();
            fast = (fast + nums[fast]) % nums.size();
            fast = (fast + nums[fast]) % nums.size();
        }while(slow != fast);

        // Calculate the length, if length <= 1, return false
        int l = 0;
        do {
            slow = (slow + nums[slow]) % nums.size();
            ++l;
        }while(slow != fast);

        if(l <= 1) return false;

        // Check forward or backward, if two directions, return false
        bool positive = false, negative = false;
        do {
            if(nums[slow] > 0) positive = true;
            else negative = true;

            if(positive & negative) return false;
            a
            slow = (slow + nums[slow]) % nums.size();
        }while(slow != fast);

        return true;
    }
};

Trial 2

我們可以把上面的解法變成對每個 index 都當作開頭，雖然要花 O(n^2) 的時間，但至少可以解掉 [3,1,2] 這種 case。

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        if(nums.size() < 2) return false;
        for(int i = 0; i < nums.size(); ++i) {
            if(circularStartFromIdx(nums, i))
                return true;
        }

        return false;
    }

private:
    bool circularStartFromIdx(vector<int>& nums, int idx) {
        // Find the loop
        int slow = idx, fast = idx;

        do {
            slow = (slow + nums[slow]) % nums.size();
            fast = (fast + nums[fast]) % nums.size();
            fast = (fast + nums[fast]) % nums.size();
        }while(slow != fast);

        // Calculate the length, if length <= 1, return false
        int l = 0;
        do {
            slow = (slow + nums[slow]) % nums.size();
            ++l;
        }while(slow != fast);

        if(l <= 1) return false;

        // Check forward or backward, if two directions, return false
        bool positive = false, negative = false;
        do {
            if(nums[slow] > 0) positive = true;
            else negative = true;

            if(positive & negative) return false;

            slow = (slow + nums[slow]) % nums.size();
        }while(slow != fast);

        return true;
    }
};

不過，上面的解法還是會掛在 [-1,-1,-1]。

Trial 3

後來發現，上面的解法會掛在 [-1,-1,-1]是因為我沒有 handle 好往負方向移動的情況，稍微修改一下程式碼就可以過了：

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        if(nums.size() < 2) return false;
        for(int i = 0; i < nums.size(); ++i) {
            if(circularStartFromIdx(nums, i))
                return true;
        }

        return false;
    }

private:
    bool circularStartFromIdx(vector<int>& nums, int idx) {
        // Find the loop
        int slow = idx, fast = idx;

        do {
            slow = (slow + nums[slow] + nums.size()) % nums.size();
            fast = (fast + nums[fast] + nums.size()) % nums.size();
            fast = (fast + nums[fast] + nums.size()) % nums.size();
        }while(slow != fast);

        // Calculate the length, if length <= 1, return false
        int l = 0;
        do {
            slow = (slow + nums[slow] + nums.size()) % nums.size();
            ++l;
        }while(slow != fast);

        if(l <= 1) return false;

        // Check forward or backward, if two directions, return false
        bool positive = false, negative = false;
        do {
            if(nums[slow] > 0) positive = true;
            else negative = true;

            if(positive & negative) return false;

            slow = (slow + nums[slow] + nums.size()) % nums.size();
        }while(slow != fast);

        return true;
    }
};

可惜效率不是很高： Runtime: 48 ms, faster than 13.61% of C++ online submissions for Circular Array Loop. Memory Usage: 8.5 MB, less than 80.00% of C++ online submissions for Circular Array Loop.

解法一 - Fast & Slow Pointer

using namespace std;

#include <iostream>
#include <vector>

class CircularArrayLoop {
 public:
  static bool loopExists(const vector<int> &arr) {
    for (int i = 0; i < arr.size(); i++) {
      bool isForward = arr[i] >= 0;  // if we are moving forward or not
      int slow = i, fast = i;

      // if slow or fast becomes '-1' this means we can't find cycle for this number
      do {
        slow = findNextIndex(arr, isForward, slow);  // move one step for slow pointer
        fast = findNextIndex(arr, isForward, fast);  // move one step for fast pointer
        if (fast != -1) {
          fast = findNextIndex(arr, isForward, fast);  // move another step for fast pointer
        }
      } while (slow != -1 && fast != -1 && slow != fast);

      if (slow != -1 && slow == fast) {
        return true;
      }
    }

    return false;
  }

 private:
  static int findNextIndex(const vector<int> &arr, bool isForward, int currentIndex) {
    bool direction = arr[currentIndex] >= 0;
    if (isForward != direction) {
      return -1;  // change in direction, return -1
    }

    // wrap around for negative numbers
    int nextIndex = (currentIndex + arr[currentIndex] + arr.size()) % arr.size();

    // one element cycle, return -1
    if (nextIndex == currentIndex) {
      nextIndex = -1;
    }

    return nextIndex;
  }
};

int main(int argc, char *argv[]) {
  cout << CircularArrayLoop::loopExists(vector<int>{1, 2, -1, 2, 2}) << endl;
  cout << CircularArrayLoop::loopExists(vector<int>{2, 2, -1, 2}) << endl;
  cout << CircularArrayLoop::loopExists(vector<int>{2, 1, -1, -2}) << endl;
}