Detect cycle in an array

Detect cycle in an array

Given an array of integers where each element points to the index of the next element 

how would you detect if there is a cycle in this array

Note: if the element of array is in range[0, n-1], where n is the length of array, then there must be at least one cycle.

Thus, the element may be negative or out of range[0,n-1]

For a particular index, use two pointers, one pointer moves one step each time, the other pointer move two steps each time.

If the pointers ever meet together (besides the start point) before one of the pointer reaches the end, then there is a loop. 

Otherwise, there isn't.

O(n) time, O(1) space

solution2:

use two sets, one is to record all visited index in the array, another one is to record the visited index in current possible cycle

O(n) time, O(n) space

	bool DetectCycle1(int arr[], int len) {
	int slow = 0;
	int fast = 0;
	int cur = 0;
	while (cur < len) {
	if (arr[slow] >= 0 && arr[slow] < len) {
	slow = arr[slow];
	} else {
	++slow;
	fast = slow;
	cur = slow;
	continue;
	}
	int i = 0;
	while (i < 2 && arr[fast] >= 0 && arr[fast] < len) { //move fast two steps one time
	fast = arr[fast];
	++i;
	}
	if (i < 2) { //less than two steps
	++fast;
	slow = fast;
	cur = fast;
	} else { //already move two steps
	if (fast == slow) { //if a cycle exists, they must meet
	return true;
	}
	}
	}
	return false;
	}
	bool DetectCycle2(int arr[], int len) {
	unordered_set<int> s, visited;
	for (int i = 0; i < len; ++i) {
	if (visited.find(i) == visited.end()) { //i is not visited
	int curr = i;
	while (curr >= 0 && curr < len) { // a cycle only occur in this range
	if (s.find(curr) != s.end()) { //find a visted index
	return true;
	}
	s.insert(curr);
	visited.insert(curr);
	curr = arr[curr];
	}
	s.clear();
	}
	}
	return false;
	}
	int main() {
	int c[4] = {-1,2,3,1};
	int e[4] = {3,-2,-3,0};
	int f[3] = {-1,2,3};
	cout<<DetectCycle2(c,4)<<endl;
	cout<<DetectCycle2(e,4)<<endl;
	cout<<DetectCycle2(f,3)<<endl;
	cout<<DetectCycle1(c,4)<<endl;
	cout<<DetectCycle1(e,4)<<endl;
	cout<<DetectCycle1(f,3)<<endl;;
	return 0;
	}