circular-array-loop.py

# Time: O(n)
# Space: O(1)

# You are given an array of positive and negative integers.
# If a number n at an index is positive, then move forward n steps.
# Conversely, if it's negative (-n), move backward n steps.
# Assume the first element of the array is forward next to the last element,
# and the last element is backward next to the first element.
# Determine if there is a loop in this array.
# A loop starts and ends at a particular index with more than 1 element along the loop.
# The loop must be "forward" or "backward'.
#
# Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.
#
# Example 2: Given the array [-1, 2], there is no loop.
#
# Note: The given array is guaranteed to contain no element "0".
#
# Can you do it in O(n) time complexity and O(1) space complexity?

class Solution(object):
 def circularArrayLoop(self, nums):
 """
 :type nums: List[int]
 :rtype: bool
 """
 def next_index(nums, i):
 return (i + nums[i]) % len(nums)

 for i in xrange(len(nums)):
 if nums[i] == 0:
 continue

 slow, fast = i, i
 while nums[next_index(nums, slow)] * nums[i] > 0 and \
 nums[next_index(nums, fast)] * nums[i] > 0 and \
 nums[next_index(nums, next_index(nums, fast))] * nums[i] > 0:
 slow = next_index(nums, slow)
 fast = next_index(nums, next_index(nums, fast))
 if slow == fast:
 if slow == next_index(nums, slow):
 break
 return True

 slow, val = i, nums[i]
 while nums[slow] * val > 0:
 tmp = next_index(nums, slow)
 nums[slow] = 0
 slow = tmp

 return False