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.

## 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