Circular Array Loop
Intuition
Solution
class Solution(object):
def circularArrayLoop(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
visited = [False] * len(nums)
for i in range(len(nums)):
if visited[i]:
continue
current = set()
index = i
direction = nums[i] > 0
while True:
if index in current:
loops = set()
while index not in loops:
loops.add(index)
index = (index + nums[index]) % len(nums)
tmp = [nums[j] > 0 for j in loops]
if False in tmp and True in tmp:
break
return True
elif visited[index]:
break
current.add(index)
visited[index] = True
tmp = (index + nums[index]) % len(nums)
if tmp == index:
break
index = tmp
return False
# Test
import unittest
class TestSolution(unittest.TestCase):
def test_case_1(self):
nums = [2, -1, 1, 2, 2]
self.assertTrue(
Solution().circularArrayLoop(nums)
)
def test_case_2(self):
nums = [-1, 2]
self.assertFalse(
Solution().circularArrayLoop(nums)
)
def test_case_3(self):
nums = [1, -1]
self.assertFalse(
Solution().circularArrayLoop(nums)
)
def test_case_4(self):
nums = [-1,2,1,2]
self.assertTrue(
Solution().circularArrayLoop(nums)
)
if __name__ == '__main__':
unittest.main()