Circular Array Loop

This is No.457 in LeetCode.

The solution is post below:

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        if (nums == null || nums.length < 2) return false;

        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                continue;
            }
            // slow/fast pointer
            int j = i, k = getIndex(i, nums);
            while (nums[k] * nums[i] > 0 && nums[getIndex(k, nums)] * nums[i] > 0) {
                if (j == k) {
                    // check for loop with only one element
                    if (j == getIndex(j, nums)) {
                        break;
                    }
                    return true;
                }
                j = getIndex(j, nums);
                k = getIndex(getIndex(k, nums), nums);
            }
            // loop not found, set all element along the way to 0
            j = i;
            int val = nums[i];
            while (nums[j] * val > 0) {
                int next = getIndex(j, nums);
                nums[j] = 0;
                j = next;
            }
        }
        return false;
    }

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

I think this problem is interesting and this is a good application on slow&fast pointer, so I will review it here for understanding better.

First we will check the length of nums, if the length is too short then we can’t get a loop which is longer than 1.
And then we will traverse the whole nums, if we meet any cell is 0, then we ignore it and continue, because we can’t move forward or backward in 0.
Now we should pay attention here, we will set two pointers to solve the problem. The first pointer is slow pointer, j, which is the index of current traversing number, i. And the fast pointer, k, which is the next index of traversing after j.
When we have these two pointers (index), we need to check if their sign same.
If so, then we could use a while loop to move further. For the condition of while loop, first we should make sure that the sign of slow&fast pointers are same, and second we should make sure the sign of slow&NEXT fast pointers are same as well, because fast pointer will move twice and we should check it early.
And then we still need to check when we got the equal situation, if the length of loop is 1.
If we can’t get the equal situation, we should set the visited point as 0 for convenience.