python O(n)


  • 0
    S

    first find tries to find negative loops, second search for positive.
    each find is O(n), while traversing the path setting visited nodes to given value.
    first use 0 because it cannot be used for anything else, in next pass use -1 because all negative values are gone now.

    def find(nums, cmp, none):
        n = len(nums)
        for i in range(n):
            s = i
            l = 0
            
            while cmp(nums[s]):
                hop = (s + nums[s] % n) % n
                nums[s] = none
                if s == hop:
                    l = 0
                s = hop
                l += 1
            
            if l > 1 and nums[s] == none:
                return True
                
        return False
    
    class Solution(object):
        def circularArrayLoop(self, nums):
            return find(nums, lambda x: x < 0, 0) or find(nums, lambda x: x > 0, -1)
    

  • 0
    N

    @serine : please explain the while loop if possible :)


  • 0
    S

    Sure

    The while loop travels from element i until it hits a visited element, while calculating the length of the path. All traversed elements are marked with none value so it's not visited again, making the for+while loop run in O(n) time.

    The cmp(nums[s]) make sure we traverse only positive or negative values, because the cycles need to be forward or backward only. cmp is passed in so we can do two passes over the input. First looking for backward cycles and setting all elements to 0, then forward cycles setting visited to -1. The values are different​ because we need to know if we've hit a cycle in current direction.

    Hope that helps.


Log in to reply
 

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