I am taking courses for technical interviews and following along with this grokking the coding interview patterns. However, I noticed that one of the solutions in particular appear to be wrong, and leads me more confused on the time complexity of it.
Problem statement
An input array, nums 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:
- The same set of indices is repeated when the sequence is travesed in accordance with the aforementioned rules
- The length of the sequence is at least two.
- The loop must be in a single direction forward or backward
Constraints:
- 1 <= nums.length <= 10^4
- -5000 <= nums[i] <= 5000
- nums[i] != 0
So what is the time complexity for both algorithms? I could see it being an easy argument for either O(n^2) or O(k*n) where k is the number of iterations to determine a cycle.
Provided Solution
function circularArrayLoop(nums) {
// Set slow and fast pointer at first element.
let slow = 0, fast = 0;
let size = nums.length;
for (let i = 1; i <= size; i++) {
// Save slow pointer's value before moving.
let prev = slow;
// Move slow pointer to one step.
slow = nextStep(slow, nums[slow], size);
// Check if cycle is impossible, then set both pointers to next value
// and move to the next iteration.
if (isNotCycle(nums, prev, slow)) {
fast = i;
slow = i;
continue;
}
// This flag indicates whether we need to move to the next iteration.
let nextIter = false;
// Number of moves of fast pointer.
let moves = 2;
for (let j = 0; j < moves; j++) {
// Save fast pointer's value before moving.
prev = fast;
// Move fast pointer check cycle after every move.
fast = nextStep(fast, nums[fast], size);
// If cycle is not possible, set slow and fast to next element
// set 'next_iter' to true and break this loop.
if (isNotCycle(nums, prev, fast)) {
fast = i;
slow = i;
nextIter = true;
break;
}
}
// Move to the next iteration
if (nextIter) {
continue;
}
// If both pointers are at same position after moving both, a cycle is detected.
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, prev, pointer) {
// If signs of both pointers are different or moving a pointer takes back to the same value,
// then the cycle is not possible, we return True, otherwise return False.
if ((nums[prev] >= 0 && nums[pointer] < 0) || (Math.abs(nums[pointer] % nums.length) == 0)) {
return true;
} else {
return false;
}
}
Problem with the provided solution
The solution reassigns the slow and fast pointers to whatever i is causing there to be gaps in its checking. An easy test case to fool this algorithm is:
[3,12,10,1,1,1,1,1,1,1,-1]
My solution:
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)
}
}