Circular Array Loop

Check for cycle in array, follow cycle rules no self-loop and same direction

Circular Array Loop

Problem Statement

You are playing a game with a circular array of non-zero integers, nums. Each nums[i] tells you how many indices to move if you're currently at index i:

• If nums[i] is positive, move nums[i] steps forward.
• If nums[i] is negative, move abs(nums[i]) steps backward.

Since the array is circular, moving forward from the last element wraps you back to the first element, and moving backward from the first element wraps you to the last element.

A cycle in the array is a sequence of indices, seq, of length k, where:

• Following the movement rules produces a repeating sequence: seq[0] -> seq[1] -> ... -> seq[k-1] -> seq[0] -> ...
• Every value at nums[seq[j]] is either all positive or all negative (the direction doesn't switch partway through).
• k > 1 (a cycle must have more than one index in it — it can't just be a single index looping back to itself).

Return true if there is a cycle in nums, or false otherwise.

Note: No constraints or examples were shared for this problem. Feel free to send them so they can be added here.

Solution

This problem can be solved using Floyd's Cycle Detection (also known as the "slow and fast pointer" technique, or the "tortoise and hare" method).

Steps

• For each index in the array, we treat it as a possible starting point, and try to detect a cycle from there.
• We use two pointers, slow and fast, both starting at the current index. We also remember the initial direction (isForward), based on whether the starting value is positive or negative.
• We move slow forward by one step at a time, and fast forward by two steps at a time (using our movement rules).
• After each move, we check if the cycle's rules have been broken, using a helper function, failingCycleCondition:
  • The direction (positive or negative) must stay consistent throughout the cycle. If it ever switches, this isn't a valid cycle.
  • There must be no self-loop — meaning a single index that just points back to itself without actually moving anywhere meaningful (this happens when the step size is a multiple of the array's length, resulting in an effective move of 0).
  • If either of these rules is broken at some point, we stop checking from this starting index, and move on to try the next starting index instead.
• If at any point slow and fast land on the same index, this means we've found a valid cycle, so we return true.
• If we've tried every starting index and never found a valid cycle, we return false.

Helper Functions

• nextStep(pointer, newNum, size): calculates the next index to move to, taking into account wrapping around the circular array (using the modulo operation, and correcting for negative results).
• failingCycleCondition(nums, prevDirection, pointer): checks whether the direction has flipped, or whether we've hit a self-loop (a step that doesn't actually move us anywhere).

Code

var circularArrayLoop = function (nums) {
    let size = nums.length;
    for (let i = 0; i < nums.length; i++) {
        let slow = i;
        let fast = i;
        let isForward = nums[i] > 0;

        while (true) {

            slow = nextStep(slow, nums[slow], size);

            if (failingCycleCondition(nums, isForward, slow)) {
                break;
            }

            fast = nextStep(fast, nums[fast], size);

            if (failingCycleCondition(nums, isForward, fast)) {
                break;
            }

            fast = nextStep(fast, nums[fast], size);

            if (failingCycleCondition(nums, isForward, fast)) {
                break;
            }

            if (slow === fast) {
                return true;
            }
        }
    }

    function nextStep(pointer, newNum, size) {
        let result = (newNum + pointer) % size;

        if (result < 0) {
            result += size;
        }

        return result;
    }

    function failingCycleCondition(nums, prevDirection, pointer) {

        let currDirection = nums[pointer] > 0;

        if (prevDirection !== currDirection || Math.abs(nums[pointer] % nums.length) === 0) {
            return true;
        } else {
            return false;
        }
    }
    return false;
};