Description
Difficulty : Medium
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?
Points to be cared
Mindpath: Since the give array is guaranteed to contain no 0, we start from a index which is not zero then loop through the array.
Calculate next index and do next steps
Code blow:
func circularArrayLoop(nums []int) bool {
size := len(nums)
if size <= 1 {
return false
}
for i:=0;i<size;i++{
if nums[i] == 0{
continue
}
direction := nums[i] > 0
curIndex := i
curVal := nums[i]
counter := 1
for true{
curIndex = curIndex + curVal
if curIndex >= size {
curIndex = curIndex - size
} else if curIndex < 0 {
curIndex = curIndex + size
}
curVal = nums[curIndex]
//traveled
if nums[curIndex] == 0 {
break
}
nums[curIndex] = 0
//loop detected
if curIndex == i && counter > 1{
return true
}
// direction changed
if !((direction && curVal >0) || (!direction && curVal < 0)){
break
}
counter++
}
}
return false
}