Add 457_Circular_Array_Loop.py (qiyuangong#34)

yuchenliu15 · web-flow · commit 0c59028a1ef3 · 2020-11-02T14:26:23.000+08:00
* Add 457_Circular_Array_Loop.py, by @yuchenliu15
diff --git a/python/457_Circular_Array_Loop.py b/python/457_Circular_Array_Loop.py
@@ -0,0 +1,29 @@
+class Solution:
+    def circularArrayLoop(self, nums: List[int]) -> bool:
+        for i in range(len(nums)):
+            if nums[i] == 0:
+                continue
+            
+            # if slow and fast pointers collide, then there exists a loop
+            slow = i
+            fast = self.index(nums, slow)
+            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[self.index(nums, fast)] > 0:
+                if slow == fast and fast != self.index(nums, fast):
+                    return True
+                elif slow == fast and fast == self.index(nums, fast):
+                    break
+                slow = self.index(nums, slow)
+                fast = self.index(nums, self.index(nums, fast))
+                
+            # set path to all 0s since it doesn't work
+            runner = i
+            value = nums[runner]
+            while nums[runner] * value > 0:
+                temp = self.index(nums, runner)
+                nums[runner] = 0
+                runner = temp
+        return False
+            
+    def index(self, nums, index):
+        length = len(nums)
+        return (index + nums[index] + length) % length
