package _457;

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        // Start from every element
        for (int i = 0; i < n; i++) {
            // Mark all visited points as 0 (after loop no found),
            // continue to next loop if curr loop starts with 0
            if (nums[i] == 0) {
                continue;
            }
            int slow = i;
            int fast = nextIndex(i, nums);
            int fastNext = nextIndex(fast, nums); // The next element of fast
            // Break if the direction of fast and fastNext do change
            // or if the fast or fastNext reach 0
            while (nums[fast] * nums[i] > 0 && nums[fastNext] * nums[i] > 0) {
                slow = nextIndex(slow, nums);
                fast = nextIndex(fastNext, nums);
                fastNext = nextIndex(fast, nums);
                // If fast catch up slow
                if (slow == fast) {
                    // Single element in loop
                    if (fast == fastNext) {
                        break;
                    }
                    return true;
                }
            }
            // Set the path to 0
            slow = i;
            while (nums[slow] * nums[i] > 0) {
                nums[slow] = 0;
                slow = nextIndex(slow, nums);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] n1 = { 2, -1, 1, 2, 2 };
        System.out.println(s.circularArrayLoop(n1));
        int[] n2 = { -1, 2 };
        System.out.println(s.circularArrayLoop(n2));
        int[] n3 = { -2, 1, -1, -2, -2 };
        System.out.println(s.circularArrayLoop(n3));
    }

    private int nextIndex(int i, int[] nums) {
        int n = nums.length;
        int index = i + nums[i];
        return index >= 0 ? index % n : n + (index % n);
    }
}