Simple Python O(n) AC solution single pass


  • 0
    D

    The basic idea is, we can find a loop anywhere in the array. I choose to start from index 0, and check for loop (check if I reach back to index 0). You can do that from anywhere, and should always find a loop, if one exists.

    • Begin at index 0
    • And follow the elements to next index till you reach back index 0 or you have followed the elements 'n' times, whichever is earlier.
    • If you reach back index 0 at the end, return True, else return False
    class Solution(object):
        def circularArrayLoop(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            if not nums: return False
            
            sign = nums[0] / abs(nums[0])
            count, start, next = 0, 0, -1
            
            while count < len(nums) and next != 0:
                if nums[start] * sign < 0: return False
                next = nums[start] + start
                next %= len(nums)
                start = next
                count += 1
            
            if next == 0: return True
            return False
    

  • 0
    R

    This will return False in the following example: [-1,2,1,3,2] because the loop in it starts at index 1. The expected answer is True but the output for this code will be false..


Log in to reply
 

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