# Leetcode --- Circular Array Loop

## 457. Circular Array Loop
### Description:
You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it's negative (-k), move backward k steps. Since the array is circular, you may assume that the last element's next element is the first element, and the first element's previous element is the last element.

Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle's length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

:::info
Example :
Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.

Example :
Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.
:::

### 解法條列
1. 暴力解 O(n^2^)
2. 優化解 O(n)

### 解法細節
題目條件有:
1. 前進方向保持一致
2. loop的長度不可只有1

### Python Solution
暴力解(time limited)

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            flag = []
            index = (i + nums[i]) % len(nums)
            
            while( (index not in flag) and ((nums[index]<0) == (nums[i]<0)) ):
                if(index == i and len(flag) >= 1):
                    return True
                flag.append(index)     
                index = (index + nums[index]) % len(nums)
                
        return False 

flag用於記錄走過的index(可以想成每到一個地方便在上面立旗，也可以取為trace)

---

while( (index not in flag) and ((nums[index]<0) == (nums[i]<0)) ):

這裡有兩個條件判斷:
1. index not in flag: 若到達重複的點，代表進入一個循環，不會回到原點，因此跳出while
2. (nums[index]<0) == (nums[i]<0): 由於前進方向要相同，判斷正負號是否相等來判斷方向是否一致，不相等則跳出while

---

if(index == i and len(flag) >= 1):
    reture True

index == i是判斷是否回到原點，若回到了原點還要再判斷路線長度是否大於1 (題目規定)，
若都符合則代表有解

---
優化解

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        remain = [x for x in range(len(nums))]
        while(remain):
            i = remain[0]
            flag = []
            index = i
            
            # 3 condition
            # (index not in flag)
            # (nums[index] < 0) == (nums[i] < 0)
            # (index in remain)
            
            while( (index not in flag) and ((nums[index]<0) == (nums[i]<0)) and (index in remain) ):
                flag.append(index)
                remain.remove(index)
                index = (index + nums[index]) % len(nums)
                
            if(index in flag):
                if( (len(flag) - flag.index(index)) > 1 ):
                    return True
        return False 
            

多了remain，初始化為所有index，會一步步將所有過去曾經走過的index去掉
這樣我們每次都會得到不同的flag(或trace)，避免去重複跑曾經到過的點

---

while( (index not in flag) and ((nums[index]<0) == (nums[i]<0)) and (index in remain) ):

前兩個兩件和原本一樣，第三個條件是判斷下一個index是否在剩餘所需要確認的index中

p.s 似乎將三個條件中的後面兩個條件以()括號起來可以加速，似乎

---

if(index in flag):
    if( (len(flag) - flag.index(index)) > 1 ):
        return True

此段用於判斷若有重複出現的index，
則再進一步確認重複出現的index與原先在flag內的index的距離，若大於1則代表有解。

###### tags: `leetcode` `array` `medium` `byself`