Fast/Slow Pointers: Circular Array Loop

by Raul Bojalil

HTML

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h2 class="hover-anchor" id="Statement" data-id="e912159ba4656d694eefa773cabf35b3">Statement<a href="#Statement"><span class="anchor-link">#</span></a></h2>
<p data-id="930e64b1391429bce62c05b4da1b35e4">An input array, <code>nums</code> containing non-zero integers is given, where the value at each index represents the number of places to skip forward (if the value is positive) or backward (if the value is negative). When skipping forward or backward, wrap around if you reach either end of the array. For this reason, we are calling it a circular array. Determine if this circular array has a cycle. A cycle is a sequence of indices in the circular array characterized by the following:</p>
<ul data-id="9d84bf2226a7b1412136f518767230bc">
<li>The same set of indices is repeated when the sequence is traversed in accordance with the aforementioned rules.</li>
<li>The length of the sequence is at least two.</li>
<li>The loop must be in a single direction, forward or backward.</li>
</ul>
<p data-id="419e9e7ae7242bb5264f8b9c02c89442">It should be noted that a cycle in the array does not have to originate at the beginning. A cycle can begin from any point in the array.</p>
<p data-id="ca20951bb707c77e4acb170f3e61b689"><strong>Constraints:</strong></p>
<ul data-id="e7a23271501dd922b0e88cff9fe6c871">
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \leq</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>nums.length</code> <span class="katex"><span...

JavaScript

function circularArrayLoop(nums) {
    let size = nums.length;

    // Iterate through each index of the array 'nums'.
    for (let i = 0; i < size; i++) {
        // Set slow and fast pointer at current index value.
        let slow = i;
        let fast = i;
        // Set true in 'forward' if element is positive, set false otherwise.
        let forward = nums[i] > 0;

        while (true) {
            // Move slow pointer to one step.
            slow = nextStep(slow, nums[slow], size);
            // If cycle is not possible, break the loop and start from next element.
            if (isNotCycle(nums, forward, slow)) {
                break;
            }

            // First move of fast pointer.
            fast = nextStep(fast, nums[fast], size);
            // If cycle is not possible, break the loop and start from next element.
            if (isNotCycle(nums, forward, fast)) {
                break;
            }

            // Second move of fast pointer.
            fast = nextStep(fast, nums[fast], size);
            // If cycle is not possible, break the loop and start from next element.
            if (isNotCycle(nums, forward, fast)) {
                break;
            }

            // At any point, if fast and slow pointers meet each other,
            // it indicates that loop has been found, return true.
            if (slow === fast) {
                return true;
            }
        }
    }
    return false;
}

// A function to calculate the next step
function nextStep(pointer, value, size) {
    let result = (pointer + value) % size;
    if (result < 0) {
        result += size;
    }
    return result;
}

// A function to detect a cycle doesn't exist
function isNotCycle(nums, prevDirection, pointer) {

    // Set current direction to true if current element is positive, set false otherwise.
    let currDirection = nums[pointer] >= 0;
    // If current direction and previous direction are different or moving a pointer takes back to...