old_contents: # 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 = i
              val = nums[i]
              while nums[slow] * val > 0:
                  tmp = next_index(nums, slow)
                  nums[slow] = 0
                  slow = tmp
  
          return False
  
new_contents: # 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
  
subject: Update circular-array-loop.py