Code Implementation

class Solution:
    def arrayNesting(self, nums):
        visited = [False] * len(nums)
        max_len = 0
        
        for i in range(len(nums)):
            if not visited[i]:
                start = nums[i]
                count = 0
                while not visited[start]:
                    visited[start] = True
                    start = nums[start]
                    count += 1
                max_len = max(max_len, count)
        return max_len
      

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int n = nums.size();
        vector<bool> visited(n, false);
        int maxLen = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                int start = nums[i], count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    ++count;
                }
                maxLen = max(maxLen, count);
            }
        }
        return maxLen;
    }
};
      

class Solution {
    public int arrayNesting(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int start = nums[i], count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLen = Math.max(maxLen, count);
            }
        }
        return maxLen;
    }
}
      

var arrayNesting = function(nums) {
    let visited = new Array(nums.length).fill(false);
    let maxLen = 0;
    for (let i = 0; i < nums.length; i++) {
        if (!visited[i]) {
            let start = nums[i], count = 0;
            while (!visited[start]) {
                visited[start] = true;
                start = nums[start];
                count++;
            }
            maxLen = Math.max(maxLen, count);
        }
    }
    return maxLen;
};
      

Problem Description

Given an array nums of length n containing all the integers from 0 to n-1 in some order (a permutation), you are to find the length of the largest set S that can be constructed as follows:

• Pick any index i in nums.
• Start with S = {nums[i]}.
• Next, set j = nums[i] and add nums[j] to S.
• Repeat this process: set j = nums[j] and add nums[j] to S.
• Stop when you reach a number that is already in S (i.e., the sequence forms a cycle).

The goal is to return the size of the largest possible set S you can generate from any starting index. The key constraints are:

• Each element in nums is unique and in the range 0 to n-1.
• You cannot reuse elements within the same set S; once an element is in S, you must stop if you encounter it again.
• There is always at least one valid solution.

Thought Process

At first glance, the problem asks us to explore cycles in a permutation. We could try to build the set S from every possible starting index, following the chain until we hit a repeated element. This would mean, for each index, we follow the chain of nums until we loop back, counting the size of the set.

However, if we naively do this for every index, we might repeat work, since cycles overlap and every element belongs to exactly one cycle. To optimize, we can use a visited array to track which elements we've already included in some set S. Once an element is visited, we know its cycle has already been counted, so we can skip it in future iterations.

This transition from brute-force (re-exploring cycles) to optimization (marking visited) is the key insight that turns a potentially slow solution into an efficient one.

Solution Approach

• Step 1: Initialize
  • Create a visited array of the same length as nums, initialized to False (or false).
  • Keep a variable maxLen to track the largest set size found.
• Step 2: Iterate through each index
  • For each index i from 0 to n-1:
  • If visited[i] is True, skip to the next index (we've already processed its cycle).
  • If visited[i] is False, start a new set S from this index.
• Step 3: Follow the cycle
  • Set start = nums[i] and initialize a count variable to zero.
  • While visited[start] is False:
    • Mark visited[start] as True.
    • Move to start = nums[start].
    • Increment count by 1.
  • When a visited element is found, the cycle is complete.
• Step 4: Update the result
  • After each cycle, update maxLen if count is larger than the previous maximum.
• Step 5: Return the answer
  • After all indices are processed, return maxLen as the result.

This approach ensures each element is only visited once, making the solution efficient.

Example Walkthrough

Let's use the sample input nums = [5,4,0,3,1,6,2].

1. Start at index 0:
   • nums[0] = 5 → nums[5] = 6 → nums[6] = 2 → nums[2] = 0
   • Now, back to 0, which is already visited — cycle complete.
   • Cycle: 5 → 6 → 2 → 0 (length 4)
2. Start at index 1:
   • nums[1] = 4 → nums[4] = 1
   • Now, back to 1 — cycle complete.
   • Cycle: 4 → 1 (length 2)
3. Start at index 3:
   • nums[3] = 3
   • Now, back to 3 — cycle complete.
   • Cycle: 3 (length 1)
4. Other indices (2, 4, 5, 6) are already visited in previous cycles, so we skip them.

The largest set found is of length 4.

Time and Space Complexity

• Brute-force Approach:
  • For each index, follow the cycle without marking visited.
  • Each cycle may be traversed multiple times, leading to O(n^2) in the worst case.
• Optimized Approach (with visited array):
  • Each element is visited at most once, so the total number of steps is O(n).
  • Space complexity is O(n) for the visited array.

Thus, the optimized approach is linear time and space.

Summary

The Array Nesting problem is about finding the longest cycle in a permutation array by following chains of indices. By marking elements as visited, we avoid redundant work and ensure each cycle is only counted once. The result is an elegant and efficient O(n) solution that leverages the properties of permutations and cycle detection.