Circular Array Loop

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #inspiring, #game, #backtracking, #circulararray

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?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/circular-array-loop ## Basic Ideas: Loop from left to right ## We mark dead end as 0 ## For each node, we keep going. ## It stops, when they go into different directions or hit a dead end ## If true, backtracking and mark all previous nodes as dead end ## If we visit ourself again, it's loop ## ## Note: The loop don't have to start with the first element ## ## Sample Data: [1, -1] can't be a valid loop. ## Yes, it has 2 elements. But it should have only one direction. "forward" or "backward" ## ## Complexity: Time O(n), Space O(1) class Solution(object): def circularArrayLoop(self, nums): """ :type nums: List[int] :rtype: bool """ length = len(nums) if length == 0: return False for i in range(length): is_forward = 1 if nums[i]>0 else -1 nums[i] = nums[i]%length if is_forward == -1 and nums[i] != 0: nums[i] -= length for i in range(length): # skip the checked dead ends if nums[i] == 0: continue is_forward = 1 if nums[i]>0 else -1 prev, k = nums[i], (i+nums[i])%length while k!=i and nums[k]!=0 and nums[k]*is_forward>0: prev, k = nums[k], (k+nums[k])%length if k==i: return True # backtrack and mark nodes as dead end prev = -prev while True: nums[k] = 0 prev, k = -nums[prev], (k+prev)%length if k==i: break nums[i] = 0 return False