General analysis with O(n) Python solution


  • 0
    A

    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
    

Log in to reply
 

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