Fast & Slow Pointers: Circular Array Loop: Solution Incorrect:

Courses
,
1

Soultion start and fast pointers get reassigned to whatever i is upon finding that the current traversal doesn’t end in a valid cycle. Leaves gaps in its checking.

Test Case Example: (Expected True)
[3,12,10,1,1,1,1,1,1,1,-1]

This was the solution I came up with which could be argued to be O(N^2) or O(K*N) which should reduce to O(N).
function circularArrayLoop(nums)
{
// your code will replace this placeholder return statement

//Iterate through every number in the array
for(let start = 0;  start < nums.length; start++)
{

    //Using fast and slow pointers check for a cycle
    let slow = start, fast = getIndexWithinRange(start, nums[start], nums.length);

    //Get the direction of travel from our slow pointer
    let isPositiveDirection = getIndexWithinRange(slow, nums[slow], nums.length) > 0;
    //Initialize or changedDirections to be false.
    let changedDirections = false;
    
    // If the while loop executes at least once, we are guaranteed to have a sequence of at least 2
    let sequenceLengthAtLeastTwo = false;

    while(slow !== fast)
    {
        sequenceLengthAtLeastTwo = true;

         //Check if at any point in time we go from backwards to forwards moving if so break out of while loop
         if(isPositiveDirection === true && (nums[slow] < 0 || nums[fast] < 0))
         {
             changedDirections = true;
             break;
         }
         else if(isPositiveDirection === false && ( nums[slow] > 0 || nums[fast] > 0 ) )
         {
             changedDirections = true;
             break;
         }
         
         //Iterate our slow pointer by a factor of 1, fast by 2
         slow = getIndexWithinRange(slow,nums[slow], nums.length);
         let temp = getIndexWithinRange(fast,nums[fast], nums.length);
         fast = getIndexWithinRange(temp,nums[temp], nums.length);
    }

    if(slow === fast && !changedDirections && sequenceLengthAtLeastTwo)
    {
        return true;
    }

}

return false;

}

function getIndexWithinRange(currentIndex, numToJump, lengthOfArray)
{
const desiredIndex = currentIndex + numToJump;

//if desired jump is somewhere between the bounds of the array return that
if(desiredIndex >= 0 && desiredIndex <= lengthOfArray-1)
{
    return desiredIndex;
}

//If desiredJump is negative
else if(desiredIndex < 0)
{
    //Check if we get a zero after preforming a modulus operation, if so avoid adding the length of the array
   return (desiredIndex % lengthOfArray) === 0 ? (desiredIndex % lengthOfArray) * -1 : (desiredIndex % lengthOfArray) + lengthOfArray;
}
//If desiredJump is positive, and greater than the length of the array
if(desiredIndex > lengthOfArray-1)
{
    return desiredIndex % (lengthOfArray)
}

}

Course: Grokking Coding Interview Patterns in JavaScript - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-javascript/7DXglWwvEpB

2

Hello @Tobi_Bratcher,

Thank you for pointing that out. We have fixed the issue and updated the course.

Happy Learning.

1 Like