# LeetCode 565: Array Nesting

## Problem Restatement

We are given an integer array `nums` of length `n`.

The array is a permutation of the numbers from `0` to `n - 1`. That means every value appears exactly once.

For each starting index `k`, we build a set:

```python
s[k] = {
    nums[k],
    nums[nums[k]],
    nums[nums[nums[k]]],
    ...
}
```

We stop right before a duplicate value would be added.

Return the largest possible size of `s[k]`.

The constraints are `1 <= nums.length <= 10^5`, `0 <= nums[i] < nums.length`, and all values in `nums` are unique. The examples include `nums = [5,4,0,3,1,6,2]`, output `4`, and `nums = [0,1,2]`, output `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A permutation array `nums` |
| Output | Length of the largest nesting set |
| Rule | Use each value as the next index |
| Stop condition | Stop before adding a duplicate value |

Example function shape:

```python
def arrayNesting(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [5, 4, 0, 3, 1, 6, 2]
```

Start at index `0`.

The sequence is:

```python
nums[0] = 5
nums[5] = 6
nums[6] = 2
nums[2] = 0
nums[0] = 5
```

Before adding duplicate `5`, the set is:

```python
{5, 6, 2, 0}
```

Its length is:

```python
4
```

So the answer is:

```python
4
```

Example 2:

```python
nums = [0, 1, 2]
```

Each index points to itself:

```python
nums[0] = 0
nums[1] = 1
nums[2] = 2
```

Every nesting set has length `1`.

So the answer is:

```python
1
```

## First Thought: Simulate From Every Index

A direct solution is to start from every index and follow the chain until a duplicate appears.

For each start, we can use a set to remember values already seen in that chain.

This works, but it repeats work.

If one starting index enters a cycle, every other index in the same cycle will produce the same cycle length. We should not traverse that cycle again.

## Key Insight

Because `nums` is a permutation, every index has exactly one outgoing edge:

```python
i -> nums[i]
```

Every value is also unique, so every index has exactly one incoming edge.

This means the array forms disjoint cycles.

The problem asks for the length of the largest cycle.

Once we traverse a cycle, every index in that cycle is fully processed. Starting from any of them again cannot give a new answer.

So we keep a global `visited` array.

## Algorithm

1. Create a boolean array `visited` of length `n`.
2. Initialize `ans = 0`.
3. For each index `i`:
   1. If `i` is already visited, skip it.
   2. Otherwise, follow the chain:
      ```python id="x33vix"
      i -> nums[i] -> nums[nums[i]] -> ...
      ```
   3. Count how many unvisited indices are reached.
   4. Mark each reached index as visited.
   5. Update `ans`.

## Correctness

Since `nums` is a permutation of `0` through `n - 1`, following the rule `i = nums[i]` can never leave the valid index range.

Because there are only finitely many indices, the sequence must eventually repeat. Since every value is unique, the repeated structure is a cycle.

For any starting index inside a cycle, following `nums` visits exactly the indices in that cycle before returning to the start. Therefore, the length of the nesting set is exactly the cycle length.

The algorithm traverses each unvisited cycle once, counts its length, and marks all indices in it as visited. Later starts inside the same cycle are skipped, which does not lose any larger answer because they have the same cycle length.

Since every index belongs to exactly one cycle, the algorithm considers every cycle exactly once and returns the largest cycle length.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is visited once |
| Space | `O(n)` | The `visited` array stores one boolean per index |

## Implementation

```python
class Solution:
    def arrayNesting(self, nums: list[int]) -> int:
        n = len(nums)
        visited = [False] * n
        ans = 0

        for i in range(n):
            if visited[i]:
                continue

            length = 0
            current = i

            while not visited[current]:
                visited[current] = True
                current = nums[current]
                length += 1

            ans = max(ans, length)

        return ans
```

## Code Explanation

We keep track of processed indices:

```python
visited = [False] * n
```

For every possible starting index:

```python
for i in range(n):
```

we skip it if it already belongs to a cycle we processed:

```python
if visited[i]:
    continue
```

Otherwise, we follow the chain:

```python
current = i

while not visited[current]:
```

Inside the loop, we mark the current index and move to the next index:

```python
visited[current] = True
current = nums[current]
length += 1
```

When we reach an already visited index, the current cycle has ended.

Then we update the best answer:

```python
ans = max(ans, length)
```

## In-Place Version

We can also mark visited indices directly inside `nums`.

Since every value is originally in the range `0` to `n - 1`, we can use `n` as a sentinel value.

This changes the input array.

```python
class Solution:
    def arrayNesting(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0

        for i in range(n):
            length = 0

            while nums[i] != n:
                next_i = nums[i]
                nums[i] = n
                i = next_i
                length += 1

            ans = max(ans, length)

        return ans
```

This version uses `O(1)` extra space, but it mutates `nums`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.arrayNesting([5, 4, 0, 3, 1, 6, 2]) == 4
    assert s.arrayNesting([0, 1, 2]) == 1
    assert s.arrayNesting([1, 2, 0]) == 3
    assert s.arrayNesting([1, 0, 3, 2]) == 2
    assert s.arrayNesting([2, 0, 1, 4, 3]) == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[5, 4, 0, 3, 1, 6, 2]` | Main sample |
| `[0, 1, 2]` | Every index is a one-cycle |
| `[1, 2, 0]` | One cycle using all indices |
| `[1, 0, 3, 2]` | Two cycles with equal length |
| `[2, 0, 1, 4, 3]` | Largest cycle is not first |