Circular Array Loop

Problem Id: 457 Difficulty: Medium


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()