const BREAKPOINT = -1;
/**
*
* @param arr
* returns true if array is circular else false.
*/
const cycleInCircularArray = (arr: Array<number>): boolean => {
const arrLength = arr.length;
const cycleCheck: any = {};
for (let index = 0; index < arrLength; index += 1) {
const isForward = arr[index] > 0;
// direction is decided on each starting index
let slow = index;
let fast = index;
while(true) {
const slowIndex = `slow-${slow}`;
const fastIndex = `fast-${fast}`;
if (slowIndex in cycleCheck && fastIndex in cycleCheck) {
// memoization check
slow = cycleCheck[slowIndex];
fast = cycleCheck[fastIndex];
if (slow === BREAKPOINT || fast === BREAKPOINT || slow === fast) {
break;
}
}
slow = findNextIndex(arr, arrLength, isForward, slow);
fast = findNextIndex(arr, arrLength, isForward, fast);
if (fast !== BREAKPOINT) { // no single cycle
fast = findNextIndex(arr, arrLength, isForward, fast)
}
// if (slow === BREAKPOINT || fast === BREAKPOINT) {
// return false -> Not gonna work, gotta try all
// }
if (slow === BREAKPOINT || fast === BREAKPOINT || slow === fast) {
break;
}
}
if (slow === fast && slow !== BREAKPOINT) {
return true
}
}
return false;
}
/**
*
* @param arr
* @param arrLength
* @param isForward
* @param currentIndex
* returns the nextIndex taking currentPosition and currentNumber
* if it finds cycle it returns BREAKPOINT i.e -1
*/
const findNextIndex = (arr: Array<number>, arrLength: number, isForward: boolean, currentIndex: number): number => {
const direction = arr[currentIndex] > 0;
if (isForward !== direction) {
return BREAKPOINT;
}
let nextIndex = (currentIndex + arr[currentIndex]) % arrLength;
if (nextIndex < 0) {
nextIndex += arrLength;
// negative offset, right?
}
if (nextIndex === currentIndex) {
return BREAKPOINT; // single node cycle
}
return nextIndex;
}
