# LintCode: Minimum Cycle Section

Minimum Cycle Section

Similar Problems:

Given an array of int, find the length of the minimum cycle section.

Notice
The length of array do not exceed 100000.
Each element is in the int range

Example

```Given array = [1,2,1,2,1,2], return 2.

Explanation:
The minimum cycle section is [1,2], and the length is 2.
```
```Given array = [1,2,1,2,1], return 2.

Explanation:
The minimum cycle section is [1,2], and the length is 2, although the last 2 is not given, we still consider the cycle section is [1,2].
```
```Given array = [1,2,1,2,1,4], return 6.

Explanation:
The minimum cycle section is [1,2,1,2,1,4], and the length is 6.
```

Github: code.dennyzhang.com

Credits To: lintcode.com

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

```## Blog link: https://code.dennyzhang.com/minimum-cycle-section
## Basic Ideas: Dynamic programming
##  dp[]: the length of the mininum cycle section from the first element to current one
##    This means for string of S[0:i], S[0:dp[i]] is the mininum cycle section
##
##  Array: 1 2 3 1 2 3 1 4
##     dp: 1 2 3 3 3 3 3 8
##
##  So dp[0] is definitely 1
##  For dp[i], we need compare S[i] with S[i%dp[i-1]].
##       If they are the same, the old cycle section still work. Thus dp[i] = dp[i-1]
##       Otherwise, the old section doesn't work.
##                 The section will always starts with S[0].
##                 If S[i] == S[0], the section will be S[0:i]. Thus dp[i]=i
##                 Otherwise, the section will be S[0:i+1]. Thus dp[i]=i+1
##
## To get dp[i], we only need dp[i-1]. Thus we can lower space complexity from O(n) to O(1)
##
## Complexity: Time O(n), Space O(1)
class Solution:
"""
@param array: an integer array
@return: the length of the minimum cycle section
"""
def minimumCycleSection(self, array):
length = len(array)
if length <= 1: return length
dp = 1
for i in range(1, length):
if array[i] != array[i%dp]:
if array[i] == array[0]: dp = i
else: dp = i+1
return dp
```

Share It, If You Like It.