**Description:**

https://leetcode.com/problems/array-nesting/description/

**Algorithm:**

Actually we are separating the array into several groups by determining S[k]. The numbers inside of S[k] will form a cycle.

For example:

**Input:** A = [5,4,0,3,1,6,2]

**Output:** 4

**Explanation:**

A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

S[5] = {A[5], A[6], A[2], A[0]} = {6, 2, 0, 5}

S[6] = {A[6], A[2], A[0], A[5]} = {2, 0, 5, 6}

S[2] = {A[2], A[0], A[5], A[6]} = {0, 5, 6, 2}

S[1] = {A[1], A[4]} = {4,1}

S[4] = {A[4], A[1]} = {1,4}

S[3] = {A[3]} = {3}

So just mark the used number in the finding process. If meets used number -> stop.

**Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public: int arrayNesting(vector<int>& nums) { int n = nums.size(); int currentIdx = 0; int maxLength = 0; int currentLength = 0; int IdxTemp = 0; for (int i = 0; i < n; i++) { currentIdx = i; currentLength = 0; while(nums[currentIdx] != -1) { IdxTemp = currentIdx; currentIdx = nums[IdxTemp]; nums[IdxTemp] = -1; currentLength++; } maxLength = currentLength > maxLength? currentLength : maxLength; } return maxLength; } }; |

**Timing & Space:**

fastest

O(n) & O(1)