-
Notifications
You must be signed in to change notification settings - Fork 119
/
Copy pathCircular Array Loop.js
50 lines (39 loc) · 1.66 KB
/
Circular Array Loop.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
var circularArrayLoop = function(nums) {
// cannot be a cycle if there are less than 2 elements
const numsLen = nums.length;
if (numsLen < 2) return false;
// init visited array
const visited = Array(numsLen).fill(false);
// check each index to see if a cycle can be produced
for (let i = 0; i < numsLen; i++) {
if (visited[i]) continue;
visited[i] = true;
// determine initial direction
const isPositive = nums[i] > 0;
// reset which indices were visited after each iteration
const visitedPerIdx = Array(numsLen).fill(false);
// reset cycle length and current index after each iteration
let cycleLen = 0,
currIdx = i;
// loop while cycle is valid
while (true) {
// break if current index moves cycle in opposite direction
if (isPositive !== nums[currIdx] > 0) break;
// calc next valid index
let nextIdx = (currIdx + nums[currIdx]) % numsLen;
// map negative index to a positive index
if (nextIdx < 0) nextIdx += numsLen;
// break if cycle points to same index
if (currIdx === nextIdx) break;
cycleLen++;
// a cycle is found when the index has already been visited in the current outer iteration, and
// the cycle length is greater than 1.
if (visitedPerIdx[nextIdx] && cycleLen > 1) return true;
visitedPerIdx[nextIdx] = true;
visited[nextIdx] = true;
// set curr index to new index
currIdx = nextIdx;
}
}
return false;
};