# General analysis with O(n) Python solution

• There are 2 contrived constraints, with out which any circular array has a loop; although not all are clearly stated in the question. Because the array has a finite number of elements, and you can always follow the links for an infinite number of steps, sooner or later you will come back to a visited place.

The constraints are:
(1) Single element loops don't count.

• [5, 5, 5, 5, 5], or [3, 9, 27] should return false.

(2) You can not change directions while following the links.

• [1, -1] should return false.

(I don't see any natural reason or significance to add those constraints, except that it makes a LeetCode problem.)

To address constraint (1), eliminate any place that immediately loops back to itself (identified by having value 0 or multiple of array length), or any place pointing to such locations transitively.

For constraint (2), filter the array into a forward array and a backward one to be searched separately. For instance, [-2, 1, -1, -2, -2] becomes forward [0, 1, 0, 0, 0] and backward [-2, 0, -1, -2, -2] (or equivalently [3, 0, 4, 3, 3]).

Finally, it's no need to use slow/fast pointers. You know there are always loops. Just check whether it contains more than 1 element. Recursively follow the links and mark places leading to a single element loop as 0. When you see the next index is smaller and the value there is not 0, you found one.

class Solution(object):
def circularArrayLoop(self, nums):
forward = map(lambda x: x % len(nums) if x > 0 else 0, nums)
backward = map(lambda x: x % len(nums) if x < 0 else 0, nums)
for i in range(len(nums)):
if follow(forward, i):
return True
if follow(backward, i):
return True
return False

def follow(nums, i):
if nums[i] == 0:
return False
nextIndex = (nums[i] + i) % len(nums)
# looped back
if nextIndex < i and nums[nextIndex] != 0:
return True
# else continue forward
ans = follow(nums, nextIndex)
if ans == False:
nums[i] = 0
return ans

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.