# Array Nesting
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/array-nesting)
Canonical: https://scaleengineer.com/dsa/problems/array-nesting
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` of length `n` where `nums` is a permutation of the numbers in the range `[0, n - 1]`.

You should build a set `s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... }` subjected to the following rule:

* The first element in `s[k]` starts with the selection of the element `nums[k]` of `index = k`.
* The next element in `s[k]` should be `nums[nums[k]]`, and then `nums[nums[nums[k]]]`, and so on.
* We stop adding right before a duplicate element occurs in `s[k]`.

Return _the longest length of a set_ `s[k]`.

**Example 1:**

**Input:** nums = [5,4,0,3,1,6,2]
**Output:** 4
**Explanation:** 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

**Example 2:**

**Input:** nums = [0,1,2]
**Output:** 1

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] < nums.length`
* All the values of `nums` are **unique**.

# Approaches
## Brute Force with Re-computation
This approach iterates through every possible starting index from `0` to `n-1`. For each starting index `k`, it simulates the process of building the set `s[k]` by following the chain of indices: `k -> nums[k] -> nums[nums[k]] -> ...`. To detect when a duplicate element occurs, a temporary data structure (like a `HashSet` or a boolean array) is used for each starting index `k`. The length of the current sequence is tracked, and the maximum length found across all starting indices is returned.
**Time:** O(n^2). The outer loop runs `n` times. In the worst-case scenario (a single cycle of length `n`), the inner `while` loop also runs up to `n` times for each starting index `i`. · **Space:** O(n). For each iteration of the outer loop, a `HashSet` is created. In the worst-case scenario of a single large cycle, this set can store up to `n` elements.
**Pros:** Simple to understand and implement as it directly follows the problem statement.
**Cons:** Highly inefficient due to redundant computations. The same cycle is traversed and its length is calculated for every element within that cycle.; High space complexity in the worst case.
### Explanation
The most straightforward way to solve the problem is to follow the problem description directly. We can iterate through each element of the array and treat it as a starting point of a sequence. For each starting point `i`, we follow the chain `nums[i]`, `nums[nums[i]]`, and so on, keeping track of the elements we've seen in this specific sequence using a `HashSet`. We continue until we encounter an element that's already in our set. The size of the set at that point gives us the length of the sequence starting at `i`. We do this for all possible starting points and keep track of the maximum length found.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int arrayNesting(int[] nums) {
        int maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> visitedInSequence = new HashSet<>();
            int count = 0;
            int j = i;
            // The sequence stops right before a duplicate element occurs.
            // The value nums[j] is the element to be added to the set.
            while (!visitedInSequence.contains(nums[j])) {
                visitedInSequence.add(nums[j]);
                count++;
                j = nums[j];
            }
            maxLength = Math.max(maxLength, count);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Iterate through each index `i` from `0` to `n-1` as a potential starting point.
- For each `i`, create a new `HashSet` to keep track of the numbers encountered in the current sequence to detect duplicates.
- Start a traversal from `j = i`.
- In a loop, as long as the value `nums[j]` has not been seen before in the current sequence:
  - Add `nums[j]` to the `HashSet`.
  - Increment a local `count`.
  - Move to the next element by updating `j = nums[j]`.
- Once a duplicate is found, the loop for the current sequence terminates.
- Update `maxLength = max(maxLength, count)`.
- After checking all starting indices, return `maxLength`.

## Optimized Traversal with a Visited Array
This approach improves upon the brute-force method by recognizing that all elements in a single cycle will produce the same length. Therefore, once we calculate the length of a cycle starting from one of its elements, we don't need to recalculate it for any other element in that same cycle. We use a global boolean `visited` array to keep track of all indices that have already been visited as part of any cycle.
**Time:** O(n). Each element of the `nums` array is visited exactly once. The outer loop iterates `n` times, but the inner `while` loop's total executions across all outer loop iterations is `n`, because each element `i` is processed only when `visited[i]` is `false`. · **Space:** O(n). We use an additional boolean array `visited` of size `n` to store the visited status of each index.
**Pros:** Efficient time complexity as it avoids redundant calculations.; Each element is processed only once.
**Cons:** Requires extra space proportional to the input size.
### Explanation
The key observation is that the input array represents a permutation, which can be decomposed into disjoint cycles. Any element within a cycle will traverse the entire cycle and yield the same length. The brute-force approach is inefficient because it recalculates this length for every element in the cycle. To optimize, we can use a `visited` array. When we start a traversal from an index `i`, we traverse its entire cycle, counting the elements. Crucially, we mark every index we visit in the `visited` array. In subsequent iterations of our main loop, if we encounter an index that is already marked as visited, we know its cycle length has already been accounted for, and we can skip it. This ensures each element in the `nums` array is visited exactly once.

```java
class Solution {
    public int arrayNesting(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Create a boolean array `visited` of size `n` and initialize all its elements to `false`.
- Loop for `i` from `0` to `n-1`:
  - If `visited[i]` is `false`:
    - This means we've found a new, unvisited cycle.
    - Initialize `count = 0` and `start = i`.
    - Start an inner loop that continues as long as `visited[start]` is `false`.
      - Mark the current element as visited: `visited[start] = true`.
      - Move to the next element in the cycle: `start = nums[start]`.
      - Increment `count`.
    - After the cycle is fully traversed, update `maxLength = max(maxLength, count)`.
- Return `maxLength`.

## Optimal Solution with In-place Marking
This is the most space-efficient approach. Instead of using an auxiliary `visited` array, it modifies the input array `nums` itself to mark visited elements. Since all original values in `nums` are within the range `[0, n-1]`, we can use a special value that falls outside this range (e.g., `n` or `-1`) to signify that an element at a particular index has been visited. This eliminates the need for extra space.
**Time:** O(n). Similar to the previous approach, each element is visited and processed exactly once. · **Space:** O(1). No extra space proportional to the input size is used. We only use a few variables for iteration and counting.
**Pros:** Optimal time and space complexity.; No extra space is required, making it very memory-efficient.
**Cons:** Modifies the input array. If the caller requires the original array to be preserved, a copy must be made first, which would negate the space savings.
### Explanation
To achieve O(1) space complexity, we can avoid the extra `visited` array by using the input array `nums` itself for marking. The problem guarantees that `0 <= nums[i] < n`. This means we can use a value outside this range, like `n` or `Integer.MAX_VALUE`, as a sentinel to mark an index as visited. The logic remains similar to the previous approach: we iterate through each index, and if it hasn't been visited, we start a traversal. During the traversal of a cycle, we overwrite the value at each visited index with our sentinel value. This way, we mark the node as visited and also retrieve the next node in the chain before the value is destroyed.

```java
class Solution {
    public int arrayNesting(int[] nums) {
        int maxLength = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Use 'n' as a visited marker since all original values are < n
            if (nums[i] != n) { 
                int start = i;
                int count = 0;
                while (nums[start] != n) {
                    int temp = start;
                    start = nums[start];
                    nums[temp] = n; // Mark the element at index 'temp' as visited
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Let `n = nums.length`.
- Loop for `i` from `0` to `n-1`:
  - Choose a special marker value that is outside the valid range of indices, for example, `n`.
  - If the value at `nums[i]` has not been marked as visited (i.e., `nums[i] != n`):
    - Start traversing a new cycle from `start = i`.
    - Initialize `count = 0`.
    - Start an inner loop that continues as long as `nums[start]` is not the visited marker.
      - Store the next index: `nextIndex = nums[start]`.
      - Mark the current index as visited by setting `nums[start] = n`.
      - Move to the next index: `start = nextIndex`.
      - Increment `count`.
    - Update `maxLength = max(maxLength, count)`.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution { public int arrayNesting ( int [] nums ) { int ans = 0 , n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { int cnt = 0 ; int j = i ; while ( nums [ j ] < n ) { int k = nums [ j ]; nums [ j ] = n ; j = k ; ++ cnt ; } ans = Math . max ( ans , cnt ); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int arrayNesting ( vector < int >& nums ) { int ans = 0 , n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { int cnt = 0 ; int j = i ; while ( nums [ j ] < n ) { int k = nums [ j ]; nums [ j ] = n ; j = k ; ++ cnt ; } ans = max ( ans , cnt ); } return ans ; } };
```

### Python

```python
class Solution : def arrayNesting ( self , nums : List [ int ]) -> int : ans , n = 0 , len ( nums ) for i in range ( n ): cnt = 0 while nums [ i ] != n : j = nums [ i ] nums [ i ] = n i = j cnt += 1 ans = max ( ans , cnt ) return ans
```