Circular Array Loop#

Given a circular array nums containing positive and negative integers, move forward k indices if the number k at a certain index is positive, and move backward k indices if the number is negative -k. Because the array is circular, you can assume that the next element after the last element is the first element, and the previous element before the first element is the last element, to determine whether there is a loop or a cycle in nums. The loop must start and end at the same index, and the length of the loop must be >1. Additionally, all movements within a loop must be in the same direction, in other words, a loop cannot include both forward and backward movements at the same time.

Example#

Solution#

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var circularArrayLoop = function(nums) {
    var n = nums.length;
    var getNext = x => {
        var nextIndex = (x+nums[x])%n;
        return nextIndex >= 0 ? nextIndex : nextIndex+n;
    };
    for(let i=0;i<n;++i) {
        if(nums[i] === 0) continue;
        let slow = i;
        let fast = getNext(i);
        while(nums[slow]*nums[fast] > 0 && nums[fast] * nums[getNext(fast)] > 0){
            if(slow === fast){
                if(slow === getNext(slow)) break;
                else return true;
            }
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        let tmp = i;
        let val = nums[tmp];
        while(val * nums[tmp] > 0){
            let k = getNext(tmp);
            nums[tmp] = 0;
            tmp = k;
        }
    }
    return false;
};

Idea#

First of all, let's explain the meaning of the problem. Taking the example [2,-1,1,2,2] as an example, initially the index 0 has a value of 2, then move forward 2 steps to index 2 with a value of 1, then move forward 1 step to reach index 3 with a value of 2, and then move forward 2 steps to loop back to index 0, completing one loop. The starting point here is not necessarily index 0, the starting point can be any index position. Secondly, the limiting condition is that the length of the loop must be greater than 1, and all movements within a loop must be in the same direction. This problem uses the technique of slow and fast pointers. The fast pointer moves two steps each time, and the slow pointer moves one step each time. If a loop can be achieved, then the slow and fast pointers will definitely meet. Of course, in this case, one step and two steps refer to moving a step of nums[i], not moving to index+1. First, define n as the length of the array and getNext as the method to get the index value of the next step. Then traverse the array. According to the definition, the array cannot contain 0 elements, so pruning is done using 0 as a mark value. Set the slow pointer to point to i and the fast pointer to point to the index of the next step. In the while loop, the first judgment ensures that the signs of the array values pointed to by the slow and fast pointers are the same, and the second judgment ensures that the array value pointed to by the fast pointer and the next array value pointed to by the fast pointer are of the same sign, ensuring that all movements within a loop must be in the same direction. After the slow and fast pointers meet, it is judged whether the length of the loop is 1. If the length of the loop is 1, it does not meet the condition, and the search continues; otherwise, it can be inferred that there is a loop in the array. After that, the slow pointer takes one step and the fast pointer takes two steps. Finally, pruning is needed because the elements that have been traversed cannot appear in the loop, so every step starting from index i is set to 0 to achieve pruning.

Daily Topic#

Reference#